Problème
Écrivez une multiplication a × b = c et regardez l'ensemble des chiffres de a, b et c. L'égalité est n-pandigitale lorsque ces chiffres sont 1, 2, ..., n, chacun utilisé exactement une fois (pas de zéro). Pour n = 4, 3 × 4 = 12 convient. Trouvez tous les produits c qui apparaissent dans au moins une égalité n-pandigitale.
Implémentez pandigital_products(n).
Entrée
n : le plus grand chiffre à utiliser.
Sortie
Renvoyez la somme des produits c distincts. Un produit obtenu par plusieurs égalités n'est compté qu'une fois. S'il n'y en a aucun, renvoyez 0.
Contraintes
1 ≤ n ≤ 9
Exemples
Entrée :
n = 4
Sortie attendue :
expected = 12
Entrée :
long long n = 4;
Sortie attendue :
long long expected = 12;
Entrée :
long n = 4;
Sortie attendue :
long expected = 12;
Explication
3 × 4 = 12 utilise 1, 2, 3, 4 une fois chacun, et c'est la seule égalité de ce type, donc la réponse est 12.
Entrée :
n = 3
Sortie attendue :
expected = 0
Entrée :
long long n = 3;
Sortie attendue :
long long expected = 0;
Entrée :
long n = 3;
Sortie attendue :
long expected = 0;
Explication
Avec les chiffres 1, 2, 3, les seuls découpages sont du type 1 × 2 = 3, ce qui est faux, donc la réponse est 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Toute égalité n-pandigitale est une permutation des chiffres de 1 à n découpée en trois morceaux.
Indice 2
Essayez chaque paire de points de coupe et vérifiez si le produit des deux premiers morceaux donne le troisième.
Indice 3
Stockez les produits dans un ensemble pour que chacun ne soit ajouté qu'une fois.
Complexité attendue
temps O(n! × n²), espace supplémentaire O(number of products), proportionnel au nombre de produits
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.