נתון מערך a המלא במספרים שלמים אי-שליליים. ומספר שלם חיובי k.
יש למצוא את תת-המערך (sub-array) הקטן ביותר שהסכום שלו גדול מהמספר k, ולהחזיר את האורך של תת-המערך הזה. אם אין תת-מערך כזה (כלומר, הסכום של כל איברי המערך עדיין קטן מהמספר k), יוחזר הערך a.length + 1 (אורך המערך ועוד 1).
להזכירכם - בתת-מערך האיברים סמוכים זה לזה (רציפים).
לדוגמה, אם המערך a הוא:
| 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 4 | 13 | 6 | 0 | 19 |
k = 22 יוחזר הערך 3 כי תת-המערך הקטן ביותר הוא {4, 13, 6}.k = 42 יוחזר הערך 6 כי תת-המערך הקטן ביותר הוא המערך כולו.k = 43 יוחזר הערך 7 כי אין תת-מערך שסכום איבריו גדול מ- 43.k = 26 יוחזר הערך 4 כי תת-המערך הקטן ביותר הוא {13, 6, 0, 19}.k = 2 יוחזר הערך 1 כי הסכום של תת-המערך {4} גדול מ- 2 (וכך גם לגבי תת-מערכים {13} או {6} או {19}).יש להחזיר את אורך תת-המערך הקטן ביותר ולא את איברי תת-המערך הזה.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
יש להחזיר את אורך התת-מערך הקטן ביותר ולא את איברי התת-מערך הזה.
a = [1, 4, 13, 6, 0, 19], k = 22
3
הסבר: תת-המערך הקטן ביותר שהסכום שלו אינו גדול מ-22 הוא {4, 13, 6}.
a = [1, 4, 13, 6, 0, 19], k = 42
6
הסבר: תת-המערך הקטן ביותר שהסכום שלו אינו גדול מ-42 הוא המערך כולו.
a = [1, 4, 13, 6, 0, 19], k = 43
7
הסבר: אין תת-מערך שסכום איבריו גדול מ-43, לכן מחזירים a.length + 1.
a = [1, 4, 13, 6, 0, 19], k = 26
4
הסבר: תת-המערך הקטן ביותר שהסכום שלו אינו גדול מ-26 הוא {13, 6, 0, 19}.
a = [1, 4, 13, 6, 0, 19], k = 2
1
הסבר: הסכום של תת-המערך {4} גדול מ-2.
a = [5, 1, 3, 5, 10, 7, 4, 9, 2, 8], k = 15
2
הסבר: תת-המערך הקטן ביותר שהסכום שלו אינו גדול מ-15 הוא {7, 4, 9}.
a = [2, 3, 1, 2, 4, 3], k = 7
3
הסבר: תת-המערך הקטן ביותר שהסכום שלו אינו גדול מ-7 הוא {1, 2, 4}.
a = [1, 2, 3, 4, 5], k = 11
3
הסבר: תת-המערך הקטן ביותר שהסכום שלו אינו גדול מ-11 הוא {3, 4, 5}.
קלט:
a = [1, 4, 13, 6, 0, 19], k = 22
הפלט המבוקש:
3