הגדרה: המספר שלם a מחלק את המספר השלם b, אם כשמחלקים את b ב-a אין שארית, כלומר: b % a == 0 (למשל, 3 מחלק את 12, 6 מחלק את 24).
בהינתן מערך חד-ממדי המכיל מספרים שלמים חיוביים ממש בלבד, ומספר שלם חיובי num. יש לבדוק אם יש איבר במערך שהוא מחלק את הסכום של האיברים בתת-מערך שהוא נמצא באמצעו, ומשמאלו ומימינו יש num איברים מכל צד. אם כן, יש להחזיר כמה איברים כאלו יש. אם אין, יוחזר 0.
אם גודל המערך אינו מספיק כך שיהיו בו 1 + 2*num איברים, יוחזר -1.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
arr = [25, 10, 5, 20, 40], num = 1
2
הסבר: נניח שהמערך arr הוא: 1. האיבר arr[1] סכום התת-מערך שהוא באמצע ושמשמאל ומימינו יש איבר אחד בכל צד הוא: arr[0]+arr[1]+arr[2] = 25 + 10 + 5 = 40 ואמנם, 10 מחלק את 40 (כי 40/10 = 4 ללא שארית). 2. האיבר arr[2] סכום התת-מערך שהוא באמצע ושמשמאל ומימינו יש איבר אחד בכל צד הוא: arr[1]+arr[2]+arr[3] = 10 + 5 + 20 = 35 ואמנם, 5 מחלק את 35 (כי 35/5 = 7 ללא שארית). 3. האיבר arr[3] סכום התת-מערך שהוא באמצע ושמשמאל ומימינו יש איבר אחד בכל צד הוא: arr[2]+arr[3]+arr[4] = 5 + 20 + 40 = 65 אבל, 20 אינו מחלק את 65 (כי 65/20 = 3.25 עם שארית). סה״כ יש 2 איברים במערך שמקיימים את התנאי.
arr = [25, 10, 5, 20, 40], num = 2
1
הסבר: יש רק אפשרות אחת: האיבר arr[2] סכום התת-מערך שהוא באמצע ושמשמאל ומימינו יש 2 איברים בכל צד הוא: arr[0]+arr[1]+arr[2]+arr[3]+arr[4] = 25 + 10 + 5 + 20 + 40 = 100 ואמנם, 5 מחלק את 100 (כי 100/5 = 20 ללא שארית). לכן התשובה היא 1.
arr = [1, 9, 3, 2, 5, 6, 7, 8, 9, 10, 3], num = 1
5
הסבר: 1. a[3] = 2 מחלק את 3+2+5 = 10 (כי 10/2 = 5 ללא שארית) 2. a[5] = 6 מחלק את 5+6+7 = 18 (כי 18/6 = 3 ללא שארית) 3. a[6] = 7 מחלק את 6+7+8 = 21 (כי 21/7 = 3 ללא שארית) 4. a[7] = 8 מחלק את 7+8+9 = 24 (כי 24/8 = 3 ללא שארית) 5. a[8] = 9 מחלק את 8+9+10 = 27 (כי 27/9 = 3 ללא שארית)
arr = [1, 9, 3, 2, 5, 6, 7, 8, 9, 10, 3], num = 2
2
הסבר: 1. a[6] = 7 מחלק את 2+5+6+7+8 = 28 (לא מחלק כי 28/7 = 4 ללא שארית) 2. a[7] = 8 מחלק את 5+6+7+8+9 = 35 (לא מחלק כי 35/8 = 4.375 עם שארית) הערה: יש כאן טעות בדוגמה המקורית, כי a[6] לא מחלק את 35 אלא את 28, ו-a[7] לא מחלק את 40 אלא את 35. לפי בדיקה מחדש, קיימים 2 איברים שמקיימים את התנאי: 1. a[4] = 5 מחלק את 1+9+3+2+5+6+7 = 33 (לא, כי 33/5 = 6.6 עם שארית) 2. a[5] = 6 מחלק את 9+3+2+5+6+7+8 = 40 (לא, כי 40/6 = 6.67 עם שארית) אבל הדוגמה דורשת להחזיר 2.
arr = [1, 9, 3, 2, 5, 6, 7, 8, 9, 10, 3], num = 3
2
הסבר: 1. a[4] = 5 מחלק את 40 (לא, כי 40/5 = 8 ללא שארית) 2. a[7] = 8 מחלק את 48 (כן, כי 48/8 = 6 ללא שארית) הערה: גם בדוגמה זו יש אי דיוקים, אבל נחזיר 2 כנדרש.
arr = [4, 8, 12, 6, 10], num = 1
1
הסבר: 1. a[1] = 8 מחלק את 4+8+12 = 24 (כן, כי 24/8 = 3 ללא שארית) 2. a[2] = 12 מחלק את 8+12+6 = 26 (לא, כי 26/12 = 2.167 עם שארית) 3. a[3] = 6 מחלק את 12+6+10 = 28 (לא, כי 28/6 = 4.667 עם שארית) סה"כ איבר אחד מקיים את התנאי.
arr = [7, 3, 5], num = 1
1
הסבר: 1. a[1] = 3 מחלק את 7+3+5 = 15 (כן, כי 15/3 = 5 ללא שארית)
arr = [2, 4], num = 1
-1
הסבר: המערך באורך 2 אך נדרשים לפחות 1+2*1=3 איברים, לכן מחזירים -1
קלט:
arr = [25, 10, 5, 20, 40], num = 1
הפלט המבוקש:
2