בהינתן מערך חד-ממדי arr המלא במספרים שלמים חיוביים הממוינים בסדר לא יורד.
יש להחזיר את המספר הקטן ביותר שלא יכול להיות סכום של קבוצת מספרים מהמערך.
לדוגמה,
| 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 6 | 10 | 11 | 15 |
1 יכול להיות כי הוא הסכום של התא arr[0]. 2 יכול להיות כי הוא הסכום של התא arr[1]. 3 יכול להיות כי הוא הסכום של התאים arr[0] ו- arr[1]. 4 לא יכול להיות סכום של חלק מאיברי המערך (לאו דווקא רצופים). לכן יוחזר 4.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
המערך מלא במספרים שלמים חיוביים והוא ממוין בסדר לא יורד.
arr = [1, 2, 6, 10, 11, 15]
4
הסבר: המספרים 1, 2, 3 ניתנים לייצור כסכום של חלק מאלמנטי המערך, אך המספר 4 לא ניתן לייצור
arr = [1, 1, 1, 1]
5
הסבר: ניתן ליצור את המספרים 1, 2, 3, 4 אך לא את המספר 5
arr = [1, 1, 3, 4]
10
הסבר: ניתן ליצור את המספרים 1-9 אך לא את המספר 10
arr = [1, 3, 5, 10, 20, 40]
2
הסבר: המספר 1 ניתן ליצור אך המספר 2 לא ניתן לייצור
arr = [1, 2, 4, 10, 11, 15]
8
הסבר: ניתן ליצור את המספרים 1-7 אך לא את המספר 8
arr = [1, 2, 3, 4, 5, 6]
22
הסבר: ניתן ליצור את כל המספרים מ-1 עד 21
arr = [2, 3, 4, 6, 12]
1
הסבר: המספר 1 לא ניתן ליצור כי אין במערך האלמנט 1
arr = [1, 1, 2, 3, 5, 8, 13]
34
הסבר: זו סדרת פיבונאצ'י וניתן ליצור את כל המספרים עד 33
קלט:
arr = [1, 2, 6, 10, 11, 15]
הפלט המבוקש:
4