Étant donné un nombre, la somme de sa somme et du nombre d’origine est égale à un autre arrangement donné de nombres.

Dans cet article, nous aborderons une question fascinante impliquant les nombres et les permutations : "Une permutation dans laquelle la somme d'un nombre et d'un nombre original est égale à un autre nombre donné". Ce problème combine de manière unique la théorie des nombres et la combinatoire, ce qui en fait un défi fascinant.

Pour clarifier, étant donné un nombre d'origine et un nombre cible, nous devons trouver une permutation du nombre d'origine telle que lorsque nous ajoutons le nombre d'origine et sa permutation, nous obtenons le nombre cible.

Comprendre le problème

Essentiellement, cette question combine les concepts de permutations de nombres, de sommation et de vérification d'égalité. Le défi est de trouver la permutation correcte (ou le réarrangement des nombres) qui satisfait aux conditions fournies.

Explication de l'algorithme

L'algorithme pour résoudre ce problème est le suivant −

• Comptez la fréquence de chaque numéro dans le numéro d'origine et le numéro cible.

• Comparez les fréquences. S'ils correspondent, cela signifie qu'il existe une permutation valide. S'ils ne correspondent pas, il n'y a pas de permutation valide.

Exemple

Voici une solution C++ utilisant l'algorithme ci-dessus -

#include<bits/stdc++.h>
using namespace std;

bool isPermutation(int original, int target) {
   vector<int> countOriginal(10, 0), countTarget(10, 0);
   
   while (original > 0) {
      countOriginal[original % 10]++;
      original /= 10;
   }
   
   while (target > 0) {
      countTarget[target % 10]++;
      target /= 10;
   }
   
   for (int i = 0; i < 10; i++) {
      if (countOriginal[i] != countTarget[i]) {
         return false;
      }
   }
   
   return true;
}

int main() {
   int original = 1234;
   int target = 2468;
   
   if (isPermutation(original, target - original)) {
      cout << "Yes, there is a permutation of the original number that satisfies the condition." << endl;
   } else {
      cout << "No, there is no permutation of the original number that satisfies the condition." << endl;
   }
   
   return 0;
}

Sortie

Yes, there is a permutation of the original number that satisfies the condition.

Dans la fonction isPermutation, nous initialisons d'abord les deux vecteurs countOriginal et countTarget pour calculer respectivement la fréquence des nombres dans le nombre d'origine et le nombre cible. Nous parcourons ensuite chaque nombre dans le nombre d'origine et le nombre cible et incrémentons le nombre correspondant. Enfin, nous comparons les chiffres. S'ils correspondent, nous renvoyons vrai ; sinon, nous renvoyons faux.

La fonction principale définit le numéro d'origine et le numéro cible et vérifie s'il existe une permutation valide du numéro d'origine qui satisfait à la condition.

Exemple de cas de test

Définissons le nombre d'origine sur 1234 et le nombre cible sur 2468. La différence entre le numéro cible et le numéro d'origine est 1234. Par conséquent, nous devons vérifier s’il existe une permutation égale à 1234 lui-même. Évidemment, le nombre d'origine est une permutation de lui-même, donc le résultat sera "Oui, il existe une permutation du nombre d'origine qui satisfait la condition."

Complexité temporelle et spatiale

La complexité temporelle de cet algorithme est O(n), où n est le nombre de chiffres du nombre donné. En effet, nous examinons chaque chiffre du numéro d'origine et du numéro cible.

La complexité spatiale est O(1) car la taille des vecteurs countOriginal et countTarget est constante (10) quelle que soit la taille d'entrée.

Conclusion

Dans cet article, nous explorons un problème intéressant qui intègre les concepts de permutations, d'addition et d'égalité numérique. Nous avons implémenté une solution C++ qui exploite la fréquence des nombres dans le nombre d'origine et le nombre cible.

Ce problème constitue un défi unique et un excellent moyen de mettre en pratique vos compétences en résolution de problèmes, en particulier en théorie des nombres et en combinatoire.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!