בעיית המערך המאוזן

נגדיר: מערך חד-ממדי vec באורך n. נקרא מאוזן סביב אינדקס p כאשר 0 ≤ p ≤ n אם מתקיים שסכום האיברים במערך מהאיבר 0 עד לאיבר p-1 שווה לסכום האיברים במערך מהאינדקס p עד לאינדקס n-1.

בנוסחה מתמטית זה נכתב כך: ∑(i=0 to p-1) vec[i] = ∑(i=p to n-1) vec[i]

לדוגמא, המערך {5, 6, 1, 2, 8}:

מאוזן סביב האינדקס 2, שכן: 5+6 = 1+2+8.

כתבו את השיטה:

where המקבלת מערך חד-ממדי vec מלא במספרים שלמים, ומחזירה אינדקס שסביבו vec מאוזן. אם אין אינדקס כזה, יוחזר -1.

כתבו את השיטה:

isBalanced המקבלת מערך vec ומספר אי-שלילי k ובודקת אם vec הוא k-מאוזן.
נגדיר: מערך חד-ממדי vec באורך n. נקרא k-מאוזן סביב אינדקס p כאשר 0 ≤ p ≤ n (על-פי ההגדרה הקודמת) ואם התתי-מערכים vec[0..p-1] ו- vec[p..n-1] הם (k-1) מאוזנים. (כאן אנו קוראים מערך-1-מאוזן למה שקראנו מערך מאוזן בהגדרה הקודמת).

לדוגמא, המערך {1, 2, 2, 1, 3, 2, 1, 3, 4, -1, 3, 3} הוא 3-מאוזן שכן:

• הוא מאוזן סביב p=7    (1+2+2+1+3+2+1=3+4+-1+3+3)
• כל אחד משני החלקים של המערך (אינדקסים 0 עד 6 ואינדקסים 7 עד 11) הוא 2-מאוזן.
  • המערך {1, 2, 2, 1, 3, 2, 1} הוא 2-מאוזן סביב p=4    (1+2+2+1=3+2+1)
    • המערכים {1, 2, 2, 1} ו- {3, 2, 1} הם 1-מאוזנים.    (1+2=2+1 ,  3=2+1)
  • המערך {3, 4, -1, 3, 3} הוא 2-מאוזן סביב p=3 (10 במערך המקורי)    (3+4+-1=3+3)
    • המערכים {3, 4, -1} ו- {3, 3} הם 1-מאוזנים.    (3=4+-1 ,  3=3)

שימו לב, המערך להלן אינו 3-מאוזן:

שכן התת-מערך {4, 2} באינדקסים 10 ו-11 אינו מאוזן. אבל הוא כן 2-מאוזן.

השיטות צריכות להיות רקורסיביות ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

vec = [5, 6, 1, 2, 8],
k = 1

res = 2 true

vec = [1, 2, 2, 1, 3, 2, 1, 3, 4, -1, 3, 3],
k = 3

res = 7 true

vec = [1, 2, 2, 1, 3, 2, 1, 3, 4, -1, 4, 2],
k = 3

res = 7 false

vec = [1, 2, 2, 1, 3, 2, 1, 3, 4, -1, 4, 2],
k = 2

res = 7 true

vec = [1, 7, 3, 6, 5, 6],
k = 1

res = -1 false

vec = [3, 1, 5, 2, 2],
k = 2

res = -1 false

vec = [4, 3, 2, 1, 2, 3],
k = 1

res = -1 false

vec = [1, -1, 0, 0],
k = 2

res = 0 true