Vérifie si le nombre formé par la concaténation des éléments du tableau est un nombre haché

Dans cette question, on nous donne un tableau d'entiers. Nous devons combiner tous les éléments en un entier et vérifier s'il s'agit d'un nombre Harshad.

Avant de passer à la solution, comprenons le numéro Harshad. Tous les nombres sont des nombres Harshad, divisibles par la somme de leurs nombres. Par exemple, 12 est le nombre de Harshad car 12 est divisible par 3, qui est la somme de 1+2.

Pour résoudre ce problème, nous pouvons ajouter tous les éléments du tableau puis vérifier si le résultat est un nombre Harshad.

Énoncé du problème - On nous donne un tableau d'entiers. Nous devons combiner tous les éléments en un nombre et vérifier si le nombre combiné est un nombre Harshad.

Exemple

Entrée – arr = {1, 35, 69, 60};

sortie-oui

Explication - Le nombre résultant 1356960 est divisible par sa somme.

Entrée – arr = {1, 65, 78, 1}

Sortie – Non

Explication – Le nombre combiné 165781 n'est pas divisible par 28.

Entrée – arr = {1, 44}

sortie-oui

Explication——144 est divisible par 9.

Méthode 1

Cette méthode combine tous les éléments du tableau en une seule chaîne. Nous utiliserons ensuite la méthode stoi() pour convertir les chaînes combinées en entiers. Ensuite, on peut utiliser l'opérateur modulo pour vérifier si un nombre est divisible par la somme de ses chiffres.

Algorithme

• Définissez une variable chaîne "combinée" et initialisez-la avec une chaîne vide.

• Parcourez un tableau d'entiers. Utilisez la méthode to_string() pour convertir un nombre en chaîne. Après cela, ajoutez-le à la variable "combinée".

• Définissez la variable « somme » et initialisez-la à zéro pour stocker la somme des nombres.

• Parcourez la chaîne combinée et stockez la somme de chaque nombre.

• Convertissez les chaînes combinées en entiers à l'aide de la méthode stoi(). Ensuite, l'entier est pris modulo et une valeur booléenne est renvoyée en fonction du résultat.

Exemple

#include <iostream>
#include <vector>
using namespace std;

// function to check whether the number formed by concatenating the elements of the array is a Harshad number or not
bool isHarshadNumber(vector<int> array){
   // store the concatenated number
   string combined = "";
   // Iterate over the array
   for (auto num : array){
      // Concatenate the string
      combined += to_string(num);
   }
   // Stores the sum of digits
   int sum = 0;
   // Calculate sum of digits
   for (int i = 0; i < combined.length(); i++)
      sum += (combined[i] - '0');
   // Check if n is divisible by the sum
   return stoi(combined) % sum == 0;
}
int main(){
   // Input
   vector<int> arr{1, 35, 69, 60};
   if (isHarshadNumber(arr))
      cout << "Yes, the number formed by concatenating the array element is a Harshad number";
   else
      cout << "No, the number formed by concatenating the array element is not a Harshad number";
   return 0;
}

Sortie

Yes, the number formed by concatenating the array element is a Harshad number

Complexité temporelle - O(N) puisque nous parcourons la chaîne.

Complexité spatiale - O(1) puisque nous n'utilisons pas d'espace supplémentaire.

Méthode 2

Dans cette méthode, nous effectuerons l'opération modulo sur chaque petit bloc de l'entier combiné et vérifierons si le grand entier est divisible par sa somme.

Algorithme

• Définissez des variables de chaîne "combinées".

• Parcourez le tableau d'entiers et stockez toutes les combinaisons d'entiers dans la variable « combinée ».

• Stockez la somme des nombres dans la variable "somme"

• Utilisez une boucle pour parcourir des chaînes "combinées".

• Définissez la variable « actuelle » et initialisez-la à zéro

• Multipliez la variable « actuelle » par 10 et ajoutez la valeur numérique actuelle. Ensuite, stockez la valeur résultante dans la variable « actuelle ».

• Effectuez une opération modulo sur le « courant » et la somme.

• Lorsque toutes les itérations de la boucle sont terminées, retournez true si la valeur de la variable "current" est nulle. Renvoie false si la valeur de la variable actuelle est différente de zéro.

Exemple

#include <iostream>
#include <vector>
using namespace std;

// function to check whether the number formed by concatenating the elements of the array is a Harshad number or not
bool isHarshadNumber(vector<int> array){
   // store the concatenated number
   string combined = "";
   // Iterate over the array
   for (auto num : array){
      // Concatenate the string
      combined += to_string(num);
   }
   // Stores the sum of digits
   int sum = 0;
   // Calculate the sum of digits
   for (int i = 0; i < combined.length(); i++)
      sum += (combined[i] - '0');
   // to store the current integer
   int current = 0;
   for (int i = 0; i < combined.size(); i++) {
      // Calculate the current integer by multiplying 10 and adding the current digit
      current = current * 10 + (combined[i] - '0');
      // Check if the current integer is divisible by the sum
      current %= sum;
   }
   return current == 0;
}
int main(){
   // Input
   vector<int> arr{1, 35, 69, 0};
   if (isHarshadNumber(arr))
      cout << "Yes, the number formed by concatenating the array element is a Harshad number";
   else
      cout << "No, the number formed by concatenating the array element is not a Harshad number";
   return 0;
}

Sortie

No, the number formed by concatenating the array element is not a Harshad number

Complexité temporelle - O(N)

Complexité spatiale - O(1)

Conclusion

Nous avons appris deux manières différentes de résoudre le problème. La première méthode n'est utilisée que lorsque le tableau contient moins d'éléments, car la méthode stoi() présente certaines limites lors de la conversion de chaînes en entiers. La deuxième méthode est générale et peut être utilisée pour N éléments de tableau.

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!