חיפוש מספר במערך K-כמעט-ממויין

נגדיר: מערך חד-ממדי של מספרים שלמים נקרא "K-כמעט-ממויין" (K קבוע), אם הוא מקיים את התנאים הבאים:

  1. מערך מכיל רק מספרים אי-שליליים (כלומר, כל האיברים חיוביים או אפסים).
  2. אם מתעלמים מהאפסים במערך, נקבל מערך ממוין בסדר עולה ממש.
  3. הרצף (איברים עוקבים במערך) הארוך ביותר של אפסים הוא באורך K.

לדוגמה, המערך הבא הוא "4-כמעט-ממויין" כי אורך רצף האפסים הארוך ביותר הוא 4.

 012345678910111213141516171819
a=30047900001115019200031400

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

לדוגמה, במערך a לעיל:

  • num = 9 -> התא היחיד האפשרי הוא 5 (האינדקס של 9 במערך a)
  • num = 31 -> התא היחיד האפשרי הוא 17 (האינדקס של 31 במערך a)
  • num = 30 -> התא היחיד האפשרי הוא -1 (הערך 30 לא נמצא במערך a)

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

אילוצים:
  • המערך אינו ריק והוא K-כמעט-ממוין (מקיים את שלושת התנאים לעיל), והמספר num הוא חיובי ממש.
דוגמה 1:
קלט: 
a = [3, 0, 0, 4, 7, 9, 0, 0, 0, 0, 11, 15, 0, 19, 20, 0, 0, 31, 40, 0],
num = 9
פלט: 
5

הסבר: המספר 9 נמצא במערך באינדקס 5.

דוגמה 2:
קלט: 
a = [3, 0, 0, 4, 7, 9, 0, 0, 0, 0, 11, 15, 0, 19, 20, 0, 0, 31, 40, 0],
num = 31
פלט: 
17

הסבר: המספר 31 נמצא במערך באינדקס 17.

דוגמה 3:
קלט: 
a = [3, 0, 0, 4, 7, 9, 0, 0, 0, 0, 11, 15, 0, 19, 20, 0, 0, 31, 40, 0],
num = 30
פלט: 
-1

הסבר: המספר 30 לא נמצא במערך.

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

הסבר: המספר 5 נמצא במערך באינדקס 5.

דוגמה 5:
קלט: 
a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
num = 1
פלט: 
-1

הסבר: כל האיברים במערך הם אפסים.

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

הסבר: המספר 2 נמצא במערך באינדקס 2.

דוגמה 7:
קלט: 
a = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19],
num = 10
פלט: 
-1

הסבר: המספר 10 לא נמצא במערך.

דוגמה 8:
קלט: 
a = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18],
num = 14
פלט: 
7

הסבר: המספר 14 נמצא במערך באינדקס 7.

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

קלט:

a = [3, 0, 0, 4, 7, 9, 0, 0, 0, 0, 11, 15, 0, 19, 20, 0, 0, 31, 40, 0],
num = 9

הפלט המבוקש:

5