Problema
Trova tutte le triple di interi positivi a < b < c tali che a² + b² = c² e a + b + c = perimeter. Restituisci ogni tripla come [a, b, c], ordinate in ordine crescente prima per a e poi per b. Non includere permutazioni degli stessi lati.
Implementa pythagorean_triplets(perimeter).
Input
perimeter: La somma richiesta dei tre lati.
Output
Restituisci una lista di triple nell'ordine specificato.
Vincoli
3 ≤ perimeter ≤ 100.000. Restituisci una lista vuota se nessun triangolo soddisfa i requisiti.
Esempi
Input:
perimeter = 30
Output atteso:
expected = [
[5, 12, 13]
]Input:
long long perimeter = 30;
Output atteso:
std::vector<std::vector<long long>> expected = {
{5, 12, 13}
};Input:
long perimeter = 30;
Output atteso:
long[][] expected = new long[][] {
new long[] {5, 12, 13}
};Spiegazione
5 + 12 + 13 = 30 e 5² + 12² = 13². Questa è l'unica tripla che soddisfa i requisiti.
Input:
perimeter = 11
Output atteso:
expected = []Input:
long long perimeter = 11;
Output atteso:
std::vector<std::vector<long long>> expected = {};Input:
long perimeter = 11;
Output atteso:
long[][] expected = new long[][] {};Spiegazione
Nessuna tripla crescente di interi positivi che formi un triangolo rettangolo ha somma 11.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Un triplo valido deve soddisfare sia l’equazione di Pitagora sia la somma del perimetro.
Suggerimento 2
Usa il perimetro per limitare la ricerca invece di provare ogni ordinamento dei lati.
Suggerimento 3
Ricorda di tenere solo a < b < c, e di saltare i duplicati dovuti alle scelte simmetriche dei lati.
Complessità attesa
tempo O(n^2), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.