רצפת שורש ריבועי וחיפוש אינדקס גבול

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

myIntSqrt המקבלת כפרמטר מספר שלם לא שלילי n, ומחזירה מספר שלם המהווה את רצפת השורש הריבועי של n, כלומר המספר השלם הגדול ביותר x כך ש-x² ≤ n. (floor)

לדוגמא,

  • אם n = 16 השיטה תחזיר את הערך 4 (כי 4*4 = 16). כלומר, ל-16 יש שורש ריבועי שלם.
  • אם n = 15 השיטה תחזיר את הערך 3 (כי 3*3 = 9, 4*4 = 16 אבל n < 16). כלומר, ל-15 אין שורש ריבועי שלם.

 

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

findIndex המקבלת כפרמטר מערך arr ובו במספרים שלמים, לכל המספרים במערך מהתא הראשון (אינדקס 0) ועד התא באינדקס k, יש שורש ריבועי שלם, ולכל המספרים במערך מהתא באינדקס k+1 ועד לתא האחרון (אינדקס arr.length-1) אין שורש ריבועי שלם. השיטה צריכה להחזיר את האינדקס k.

לדוגמא,

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

0123456
410961022

אזי השיטה תחזיר את הערך 3 כי בתאים 0 עד 3 יש מספרים שיש להם שורש ריבועי שלם ובתאים 4 עד 6 יש מספרים שאין להם שורש ריבועי שלם.

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

אילוצים:
  • אסור להשתמש ב-Math.sqrt או בכל שיטה אחרת מהמחלקה Math (כלומר לממש את החישוב בעצמכם).
  • המערך אינו ריק ומכיל מספרים שלמים לא שליליים.
  • כל המספרים שיש להם שורש ריבועי שלם נמצאים ברצף, לפני כל המספרים שאין להם שורש ריבועי שלם.
  • במימוש השיטה findIndex יש להשתמש בשיטה myIntSqrt.
  • ייתכן שלכל המספרים במערך אין שורש ריבועי שלם, במקרה כזה יוחזר -1.
  • ייתכן שלכל המספרים יש שורש ריבועי שלם, במקרה כזה יוחזר אינדקס התא האחרון במערך.
דוגמה 1:
קלט: 
arr = [4, 1, 0, 9, 6, 10, 22],
n = 16
פלט: 
result:
root - 4
index - 3

הסבר: בתאים 0 עד 3 יש מספרים עם שורש ריבועי שלם (4=2², 1=1², 0=0², 9=3²). בתאים 4 עד 6 אין שורש ריבועי שלם (6, 10, 22). myIntSqrt מחזיר את רצפת השורש לכל מספר.

דוגמה 2:
קלט: 
arr = [16, 5, 3],
n = 15
פלט: 
result:
root - 3
index - 0

הסבר: רק התא באינדקס 0 מכיל מספר עם שורש ריבועי שלם (16=4²). התאים 1 ו-2 מכילים מספרים ללא שורש ריבועי שלם (5, 3).

דוגמה 3:
קלט: 
arr = [2, 7, 11],
n = 0
פלט: 
result:
root - 0
index - -1

הסבר: אין אף מספר במערך עם שורש ריבועי שלם (2, 7, 11 – אף אחד מהם אינו ריבוע שלם). לכן מוחזר -1.

דוגמה 4:
קלט: 
arr = [0, 1, 4, 9, 100],
n = 143
פלט: 
result:
root - 11
index - 4

הסבר: כל המספרים במערך הם ריבועים שלמים (0=0², 1=1², 4=2², 9=3², 100=10²). לכן מוחזר האינדקס האחרון 4.

דוגמה 5:
קלט: 
arr = [25],
n = 145
פלט: 
result:
root - 12
index - 0

הסבר: מערך באורך 1 עם מספר שהוא ריבוע שלם (25=5²). מוחזר אינדקס 0.

דוגמה 6:
קלט: 
arr = [7],
n = 1
פלט: 
result:
root - 1
index - -1

הסבר: מערך באורך 1 עם מספר שאינו ריבוע שלם (7). מוחזר -1.

דוגמה 7:
קלט: 
arr = [9, 49, 0, 17, 30, 13]
פלט: 
result:
root - 1
index - 2

הסבר: בתאים 0 עד 2 יש ריבועים שלמים (9=3², 49=7², 0=0²). מתא 3 ואילך אין (17, 30, 13). מוחזר 2.

דוגמה 8:
קלט: 
arr = [1, 4, 9, 100, 10000, 0, 18, 26],
n = 8
פלט: 
result:
root - 2
index - 5

הסבר: בתאים 0 עד 5 יש ריבועים שלמים (1=1², 4=2², 9=3², 100=10², 10000=100², 0=0²). מתא 6 ואילך אין (18, 26). מוחזר 5.

דוגמה 9:
קלט: 
arr = [3, 2, 3, 5],
n = 9
פלט: 
result:
root - 3
index - -1

הסבר: אף מספר במערך אינו ריבוע שלם (3, 2, 3, 5). מוחזר -1.

דוגמה 10:
קלט: 
arr = [36, 0, 1, 16, 31, 50],
n = 10
פלט: 
result:
root - 3
index - 3

הסבר: בתאים 0 עד 3 יש ריבועים שלמים (36=6², 0=0², 1=1², 16=4²). מתא 4 ואילך אין (31, 50). מוחזר 3.

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

קלט:

arr = [4, 1, 0, 9, 6, 10, 22],
n = 16

הפלט המבוקש:

result:
root - 4
index - 3