זוג איברים שונים עם סכום נתון במערך טווחים

a הוא מערך המכיל מספרים שלמים ממוין בסדר עולה ממש (כלומר המספרים עולים ולא זהים).

נגדיר מערך טווחים של a כמערך שנבנה באופן הבא: עבור כל רצף של מספרים עוקבים ב-a, יהיה במערך הטווחים אובייקט שמכיל שני שדות של מספרים שלמים. שדה אחד הוא המספר הקטן ביותר ברצף (smallest) והשני הוא המספר הגדול ביותר ברצף (largest). רצף יכול להיות באורך 1 או יותר.

אם הרצף באורך 1 הוא מיוצג במערך המחושב על ידי אובייקט ששני השדות שלו שווים.

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

0	1	2	3	4	5	6	7	8	9	10
3	4	5	12	19	20	100	101	102	103	104

מערך הטווחים range יהיה:

0	1	2	3
<3, 5>	<12, 12>	<19, 20>	<100, 104>

(כל אובייקט מסומן כזוג סדור עם סוגריים משולשים).

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

java

בהינתן מערך טווחים a ומספר x יש להחזיר true אם אפשר למצוא זוג איברים שונים במערך המקורי שהסכום שלהם הוא x.

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

אילוצים:

מערך הטווחים מייצג בצורה נכונה את המערך המקורי הממוין.

דוגמה 1:

קלט:

a = [[3, 5], [12, 12], [19, 20], [100, 104]],
x = 22

פלט:

true

הסבר: כי 3+19 = 22

דוגמה 2:

קלט:

a = [[3, 5], [12, 12], [19, 20], [100, 104]],
x = 113

פלט:

true

הסבר: כי 12+101 = 113

דוגמה 3:

קלט:

a = [[3, 5], [12, 12], [19, 20], [100, 104]],
x = 202

פלט:

true

הסבר: כי 100+102 = 202

דוגמה 4:

קלט:

a = [[3, 5], [12, 12], [19, 20], [100, 104]],
x = 38

פלט:

false

הסבר: כי אין זוג מספרים במערך המקורי a שסכומם 38

דוגמה 5:

קלט:

a = [[3, 5], [12, 12], [19, 20], [100, 104]],
x = 53

פלט:

false

הסבר: כי אין זוג מספרים במערך המקורי a שסכומם 53

בחר קובץ לעריכה מהתפריט בצד

נשמרLn 1, Col 1

קלט:

a = [[3, 5], [12, 12], [19, 20], [100, 104]],
x = 22

הפלט המבוקש:

true