נתון מערך חד-ממדי המלא במספרים 1 ו- 0 בלבד.
המערך מייצג נסיעה של מכוניות בכביש באופן הבא:0 מייצג מכונית שנוסעת למזרח (east) ו- 1 מייצג מכונית שנוסעת למערב (west).
נגדיר זוג מכוניות כמצטלבות (עוברות זו על פני זו) כאשר מכונית אחת נוסעת מזרחה והשניה מערבה.
בצורה מדויקת יותר – זוג מכוניות (P, Q) מצטלבות כאשר P ≤ Q, ו-P נוסעת מזרחה, ו-Q נוסעת מערבה.
בהינתן מערך a מלא בנתונים כנ"ל, יש להחזיר את מספר הזוגות של מכוניות שמצטלבות.
לדוגמא, אם המערך a הוא
| 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 0 | 1 | 1 |
יש לנו 5 זוגות של מכוניות שמצטלבות (0, 1), (0, 3), (0, 4), (2, 3), (2, 4) ולכן יוחזר 5.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
המערך מלא בנתונים שהם רק 0 ו- 1.
a = [0, 1, 0, 1, 1]
5
הסבר: הזוגות המצטלבים הם: (0,1), (0,3), (0,4), (2,3), (2,4)
a = [0, 1]
1
הסבר: יש זוג אחד בלבד של מכוניות מצטלבות: (0,1)
a = [1, 0]
0
הסבר: אין זוגות מצטלבים כי המכונית ב-1 נוסעת מערבה ואחריה המכונית ב-0 נוסעת מזרחה
a = [0, 0, 0, 1, 1, 1]
9
הסבר: כל 0 מצטלב עם כל 1, יש 3*3=9 זוגות
a = [1, 1, 1, 1]
0
הסבר: אין זוגות מצטלבים כי כל המכוניות נוסעות מערבה
a = [0, 0, 0, 0]
0
הסבר: אין זוגות מצטלבים כי כל המכוניות נוסעות מזרחה
a = [0, 1, 1, 0, 1]
4
הסבר: הזוגות המצטלבים הם: (0,1), (0,2), (0,4), (3,4)
a = [0, 0, 1, 0, 0, 1, 1]
10
הסבר: הזוגות המצטלבים הם: (0,2), (0,5), (0,6), (1,2), (1,5), (1,6), (3,5), (3,6), (4,5), (4,6) - סה"כ 10
קלט:
a = [0, 1, 0, 1, 1]
הפלט המבוקש:
5