מספר זוגות עם הפרש חסום

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

כמו כן, נתון מספר שלם k שהוא חיובי או 0.

בהינתן מערך arr ומספר שלם k כנ"ל. יש להחזיר את מספר הזוגות של תאים במערך עם אינדקסים i ו- j כך ש- j < i, וההפרש בין הערכים arr[i] ו- arr[j] קטן או שווה ל- k.

דוגמאות:

עבור המערך arr:

0	1	2	3	4	5
2	4	6	11	18	20

כאשר k = 0 או k = 1 אין זוגות מתאימים ולכן יוחזר 0.
כאשר k = 2, הזוגות המתאימים הם: (20, 18), (6, 4), (4, 2), ולכן יוחזר 3.
כאשר k = 3, גם כאן הזוגות המתאימים הם: (20, 18), (6, 4), (4, 2), ולכן יוחזר 3.
כאשר k = 7, הזוגות המתאימים הם: (20, 18), (18, 11), (11, 6), (11, 4), (6, 4), (6, 2), (4, 2), ולכן יוחזר 7.
כאשר k = 25, הזוגות המתאימים הם כל זוגות המספרים במערך, ולכן יוחזר מספר הזוגות שהוא 15.

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

אילוצים:

אפשר להניח שהמערך מלא בנתונים חוקיים ואינו null. מובטח כי המערך ממוין בסדר עולה ממש.

דוגמה 1:

קלט:

arr = [2, 4, 6, 11, 18, 20],
k = 1

פלט:

הסבר: אין זוג מספרים שההפרש ביניהם קטן או שווה ל-1.

דוגמה 2:

קלט:

arr = [2, 4, 6, 11, 18, 20],
k = 2

פלט:

הסבר: הזוגות הם (20, 18), (6, 4), (4, 2).

דוגמה 3:

קלט:

arr = [2, 4, 6, 11, 18, 20],
k = 7

פלט:

הסבר: הזוגות הם (20, 18), (18, 11), (11, 6), (11, 4), (6, 4), (6, 2), (4, 2).

דוגמה 4:

קלט:

arr = [2, 4, 6, 11, 18, 20],
k = 25

פלט:

הסבר: כל זוגות המספרים במערך חוקיים.

דוגמה 5:

קלט:

arr = [1, 2, 3, 4, 5],
k = 1

פלט:

הסבר: הזוגות בעלי הפרש בדיוק 1 הם (5,4), (4,3), (3,2), (2,1).

דוגמה 6:

קלט:

arr = [10, 20, 30],
k = 5

פלט:

הסבר: ההפרש המינימלי הוא 10, ולכן אין זוגות שההפרש ביניהם קטן או שווה ל-5.

דוגמה 7:

קלט:

arr = [5, 10, 15, 20],
k = 10

פלט:

הסבר: הזוגות הם (20,15), (15,10), (10,5) עם הפרש 5. ו-(20,10), (15,5) עם הפרש 10.

דוגמה 8:

קלט:

arr = [1, 100],
k = 50

פלט:

הסבר: הזוג היחיד (100, 1) נותן הפרש 99, שהוא גדול מ-50.

נשמרLn 1, Col 1

קלט:

arr = [2, 4, 6, 11, 18, 20],
k = 1

הפלט המבוקש: