נגדיר שלשה פיתגורית (Pythagorean triple) - כשלשה של מספרים שלמים חיוביים a, b ו-c המקיימים את משפט פיתגורס, כלומר המקיימים את המשוואה a² + b² = c².
בהינתן מערך חד-ממדי arr המלא במספרים שלמים הממוינים בסדר עולה ממש. יש להחזיר true אם במערך קיימת שלשה פיתגורית ו-false אם לא.
שימו לב, אין צורך להחזיר את השלשה הזו, אלא רק להחזיר אם יש כזו או לא.
דוגמאות:
• עבור המערך arr הבא:
| 0 | 1 | 2 | 3 | 4 |
| 1 | 3 | 4 | 5 | 6 |
יוחזר true שכן יש שלשה פיתגורית (3, 4, 5) שכן 3² + 4² = 9 + 16 = 25 = 5².
המספרים לא חייבים להיות בתאים רצופים.
• עבור המערך arr הבא:
| 0 | 1 | 2 | 3 | 4 |
| 4 | 5 | 6 | 10 | 12 |
יוחזר false שכן אין במערך אף שלשה פיתגורית.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום. רמז: הסיבוכיות הנדרשת כאן היא ריבועית.
המערך מלא במספרים חיוביים שלמים והוא ממוין בסדר עולה ממש.
arr = [1, 3, 4, 5, 6]
true
הסבר: קיימת שלשה פיתגורית (3, 4, 5) כי 3² + 4² = 9 + 16 = 25 = 5²
arr = [4, 5, 6, 10, 12]
false
הסבר: אין במערך שלשה פיתגורית
arr = [5, 12, 13]
true
הסבר: קיימת שלשה פיתגורית (5, 12, 13) כי 5² + 12² = 25 + 144 = 169 = 13²
arr = [8, 15, 17]
true
הסבר: קיימת שלשה פיתגורית (8, 15, 17) כי 8² + 15² = 64 + 225 = 289 = 17²
arr = [3, 4, 6, 8, 10]
true
הסבר: קיימת שלשה פיתגורית (6, 8, 10) כי 6² + 8² = 36 + 64 = 100 = 10²
arr = [1, 2, 3]
false
הסבר: אין שלשה פיתגורית כי 1² + 2² = 1 + 4 = 5 ≠ 9 = 3²
arr = [9, 12, 15]
true
הסבר: קיימת שלשה פיתגורית (9, 12, 15) כי 9² + 12² = 81 + 144 = 225 = 15²
arr = [7, 24, 25, 26, 30]
true
הסבר: קיימת שלשה פיתגורית (7, 24, 25) כי 7² + 24² = 49 + 576 = 625 = 25²
קלט:
arr = [1, 3, 4, 5, 6]
הפלט המבוקש:
true