ציר של מערך מיוחד

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

נגדיר מרחק (distance) בין שני תאים במערך, כהפרש בין המיקומים (האינדקסים) של התאים.

נגדיר את המערך array כמערך מיוחד (special array), אם הוא מקיים את התנאי הבא: קיים מיקום k במערך כך שאם נסכום (summarize) את המכפלה של כל אחד מהערכים שמשמאלו במרחק שלו מהמיקום k, ונסכום את המכפלה של כל אחד מהערכים שמימינו במרחק שלו מהמיקום k, שני הסכומים יהיו שווים. במקרה כזה, נקרא למיקום, הציר (pivot) של המערך.

שימו לב שכיון שהאיברים במערך הם טבעיים (שלמים חיוביים ממש), המיקום 0 והמקום האחרון במערך אינם יכולים להיות הציר של המערך.

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

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

אילוצים:
  • המערך מכיל רק מספרים טבעיים (חיוביים ממש).
  • המיקום 0 והמיקום האחרון במערך אינם יכולים להיות הציר.
  • על הפתרון להיות יעיל ככל הניתן בזמן ובמקום (מומלץ O(1) זיכרון).
דוגמה 1:
קלט: 
array = [37, 10, 15, 8, 38]
פלט: 
2

הסבר: נבדוק את המיקום k=2: אם נכפיל לכל איבר שמשמאל למיקום 2 את ערכו במרחק שלו מהציר נקבל: 37*2+10*1=84. אם נכפיל לכל איבר שמימין למיקום 2 את ערכו במרחק שלו מהציר נקבל: 8*1+38*2=84. הסכומים שווים ולכן המיקום k=2 הוא הציר של המערך.

דוגמה 2:
קלט: 
array = [37, 10, 15, 8, 2]
פלט: 
1

הסבר: נבדוק את המיקום k=1: סכום מכפלות האיברים משמאל למיקום 1 הוא: 37*1=37. סכום מכפלות האיברים מימין הוא: 15*1+8*2+2*3=37. הסכומים שווים ולכן המיקום k=1 הוא הציר של המערך.

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

הסבר: נבדוק את המיקום k=2: הסכום משמאל הוא 1*2+2*1=4 והסכום מימין הוא 4*1=4. הסכומים שווים ולכן k=2 הוא הציר של המערך.

דוגמה 4:
קלט: 
array = [1, 2, 4, 3]
פלט: 
-1

הסבר: נבדוק את k=1: הסכום משמאל הוא 1 ואילו מימין 10 (לא שווים). נבדוק את k=2: הסכום משמאל הוא 4 ואילו מימין הוא 3 (לא שווים). לכן אין ציר למערך והשיטה מחזירה -1.

דוגמה 5:
קלט: 
array = [5, 5, 5, 5, 5]
פלט: 
2

הסבר: כל האיברים במערך שווים, ולכן מתוך סימטריה הציר נמצא בדיוק באמצע המערך: k=2. סכום משמאל: 5*2+5*1=15, סכום מימין: 5*1+5*2=15. הסכומים שווים.

דוגמה 6:
קלט: 
array = [1, 1, 1, 2]
פלט: 
-1

הסבר: נבדוק את k=1: הסכום משמאל הוא 1*1=1, והסכום מימין הוא 1*1+2*2=5 (לא שווים). נבדוק את k=2: הסכום משמאל הוא 1*2+1*1=3, והסכום מימין הוא 2*1=2 (לא שווים). לכן אין ציר למערך והשיטה מחזירה -1.

דוגמה 7:
קלט: 
array = [1, 1, 1, 1, 5, 10]
פלט: 
4

הסבר: נבדוק את המיקום k=4: הסכום משמאל הוא 1*4+1*3+1*2+1*1=10, והסכום מימין הוא 10*1=10. הסכומים שווים ולכן המיקום k=4 הוא הציר של המערך, על אף שהוא לא נמצא באמצע.

דוגמה 8:
קלט: 
array = [3, 6, 2, 8, 5]
פלט: 
-1

הסבר: נבדוק את k=1: הסכום משמאל הוא 3, והסכום מימין הוא 2*1+8*2+5*3=33 (לא שווים). נבדוק את k=2: הסכום משמאל הוא 3*2+6*1=12, והסכום מימין הוא 8*1+5*2=18 (לא שווים). נבדוק את k=3: הסכום משמאל הוא 3*3+6*2+2*1=23, והסכום מימין הוא 5*1=5 (לא שווים). לכן אין ציר למערך והשיטה מחזירה -1.

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

קלט:

array = [37, 10, 15, 8, 38]

הפלט המבוקש:

2