תת-מערכים עם איברים קטנים או שווים למספר

נתון מערך חד-ממדי arr המלא מספרים שלמים. נגדיר תת-מערך (subarray) כסדרה של תאים רצופים בתוך המערך.

לדוגמה, אם המערך הוא [1, 2, 3, 4] אזי התת-מערכים שלו הם:

[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]

[2], [2, 3], [2, 3, 4]

[3], [3, 4]

[4]

ובסה"כ 10 תת-מערכים (שאינם ריקים).

(כדאי לשים לב לסדר בו כתבנו את התת-מערכים. עשוי לרמוז על דרך הפתרון)

בהינתן מערך חד-ממדי arr המכיל מספרים שלמים (חיוביים שליליים ואפסים) ומספר שלם num.

יש להחזיר כמה תת-מערכים יש למערך arr שכל האיברים שלהם קטנים או שווים ל- num.

השיטה צריכה להיות יעילה ככל הניתן מבחינת סיבוכיות הזמן וגם סיבוכיות המקום צריכה להיות קבועה O(1).

אילוצים:
  • המערך אינו ממוין.
  • אפשר להניח שכל המספרים במערך שונים זה מזה.
  • אינכם צריכים להדפיס את התת-מערכים, אלא רק להחזיר כמה יש.
דוגמה 1:
קלט: 
arr = [7, 2, 15, 8, 9, 5, 12, 20, 3],
num = 9
פלט: 
10

הסבר: התת-מערכים שכל איבריהם קטנים או שווים ל-9 הם: {5}, {7}, {2}, {2, 7}, {8}, {9}, {9, 8}, {5, 9}, {5, 9, 8}, {3}.

דוגמה 2:
קלט: 
arr = [7, 2, 15, 8, 9, 5, 12, 20, 3],
num = 1
פלט: 
0

הסבר: אין במערך אף איבר שקטן או שווה ל-1, ולכן אין אף תת-מערך שמקיים את התנאי.

דוגמה 3:
קלט: 
arr = [1, 2, 3, 4],
num = 4
פלט: 
10

הסבר: כל האיברים במערך קטנים או שווים ל-4, לכן כל 10 התת-מערכים האפשריים מקיימים את התנאי.

דוגמה 4:
קלט: 
arr = [5, 1, 3, 2, 7],
num = 4
פלט: 
6

הסבר: התת-מערכים שמקיימים את התנאי הם: {1}, {3}, {2}, {2, 3}, {3, 1}, {2, 3, 1}.

דוגמה 5:
קלט: 
arr = [10, 20, 30, 40, 50],
num = 25
פלט: 
3

הסבר: התת-מערכים שמקיימים את התנאי הם: {10}, {20}, {20, 10}

דוגמה 6:
קלט: 
arr = [1],
num = 1
פלט: 
1

הסבר: התת-מערך שמקיים את התנאי הוא {1}

דוגמה 7:
קלט: 
arr = [5, 2, 7, 3, 6],
num = 5
פלט: 
4

הסבר: התת-מערכים שמקיימים את התנאי הם: {5}, {2}, {3}, {2, 5}.

דוגמה 8:
קלט: 
arr = [-1, -2, -3, -4, -5],
num = -2
פלט: 
10

הסבר: כל האיברים במערך קטנים או שווים ל-2-, לכן כל 10 התת-מערכים האפשריים מקיימים את התנאי.

Loading...
נשמרLn 1, Col 1

קלט:

arr = [7, 2, 15, 8, 9, 5, 12, 20, 3],
num = 9

הפלט המבוקש:

10