Tous les défis
Moyen 0 résolus 0 % de réussite

Produits pandigitaux

Additionner les produits dont l'égalité a × b = c utilise chacun des chiffres de 1 à n exactement une fois.

Ce que vous allez apprendre

  • Générer les permutations des chiffres
  • Essayer tous les découpages en trois parties
  • Éliminer les doublons avec un ensemble

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

Exemple 1
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.

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.