Problema
Scrivi una moltiplicazione a × b = c e guarda tutte insieme le cifre di a, b e c. L'uguaglianza è n-pandigitale quando queste cifre sono 1, 2, ..., n, ognuna usata esattamente una volta (niente zeri). Per n = 4, 3 × 4 = 12 va bene. Trova ogni prodotto c che compare in almeno un'uguaglianza n-pandigitale.
Implementa pandigital_products(n).
Input
n: la cifra più grande da usare.
Output
Restituisci la somma dei prodotti c distinti. Un prodotto ottenuto da più uguaglianze si somma una volta sola. Se non ce ne sono, restituisci 0.
Vincoli
1 ≤ n ≤ 9
Esempi
Input:
n = 4
Output atteso:
expected = 12
Input:
long long n = 4;
Output atteso:
long long expected = 12;
Input:
long n = 4;
Output atteso:
long expected = 12;
Spiegazione
3 × 4 = 12 usa 1, 2, 3, 4 una volta ciascuno ed è l'unica uguaglianza di questo tipo, quindi la risposta è 12.
Input:
n = 3
Output atteso:
expected = 0
Input:
long long n = 3;
Output atteso:
long long expected = 0;
Input:
long n = 3;
Output atteso:
long expected = 0;
Spiegazione
Con le cifre 1, 2, 3 le uniche suddivisioni sono del tipo 1 × 2 = 3, che è falsa, quindi la risposta è 0.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ogni uguaglianza n-pandigitale è un ordinamento delle cifre da 1 a n tagliato in tre pezzi.
Suggerimento 2
Prova ogni coppia di punti di taglio e controlla se i primi due pezzi moltiplicati danno il terzo.
Suggerimento 3
Salva i prodotti in un insieme, così ognuno viene sommato una volta sola.
Complessità attesa
tempo O(n! × n²), spazio aggiuntivo O(number of products), cioè pari al numero di prodotti
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.