Trouver le plus petit nombre formé en insérant les nombres donnés

Insérer un numéro dans un numéro donné signifie ajouter un nouveau numéro au numéro donné, soit avant, après ou au milieu du numéro. On nous a donné un nombre et un nombre et nous devons ajouter ce nombre au nombre de la manière la plus petite possible. Pour faciliter l'opération d'insertion, nous allons convertir le nombre en chaîne. De plus, le nombre donné peut également être négatif, nous devons donc tenir compte de ce cas.

Exemple Exemple

Input1

Input 1

Given number: 124
Given digit: 3
Output: 1234 

Explication − Nous avons quatre endroits où nous pouvons additionner le nombre donné et le résultat peut être 3124, 1324, 1234, 1243. Des quatre, l’avant-dernier est le plus petit.

Input2

Input 2

Given number: -124
Given digit: 3
Output: -3124 

Explication − Nous avons quatre endroits où nous pouvons ajouter le nombre donné et le résultat peut être -3124, -1324, -1234, -1243. Des quatre, le premier est le plus petit.

Approche Naive

Approche Naive

Maintenant que nous avons vu l'exemple, regardons les étapes que nous allons effectuer pour résoudre le problème -

• Tout d'abord, nous vérifierons si le nombre actuel est positif ou négatif.

• Si le nombre actuel est négatif, nous le marquerons comme variable négative et rendrons le nombre actuel positif.

• Après cela, nous convertirons le nombre actuel en chaîne et appellerons la fonction selon que le nombre actuel est positif ou négatif.

• Dans ces fonctions, nous essaierons d'ajuster le nombre à chaque position et vérifierons si le nombre actuel est plus petit ou plus grand en fonction de nombres positifs ou négatifs.

• Si le nombre actuel est positif, nous essaierons de trouver le plus petit nombre et de le renvoyer.

• Sinon, on trouve le plus grand nombre et on le renvoie en multipliant par -1.

Exemple

Exemple

#include <bits/stdc++.h>
using namespace std;
int findMin(string str, int d){
   string ans = str + to_string(d); // variable to store the answer     
   // traversing over the string 
   for(int i=0; i<= str.size(); i++){
      ans = min(ans, str.substr(0,i) + to_string(d) + str.substr(i));
   }
   return stoi(ans);
}
int findMax(string str, int d){
   string ans = str + to_string(d); // variable to store the answer     
   // traversing over the string 
   for(int i=0; i<= str.size(); i++){
      ans = max(ans, str.substr(0,i) + to_string(d) + str.substr(i));
   }
   return stoi(ans);
}
int minimumNumber(int n, int d){
   // checking for the negative number 
   int isNeg = 1;    
   if(n < 0){
      n *= -1;
      isNeg = -1;
   }    
   // converting the current number to string 
   string str = to_string(n);    
   if(isNeg == 1){
      return findMin(str,d);
   }
   else{
      return -1*findMax(str,d);
   }
}
int main(){
   int n = -124; // given number 
   int d = 3; // given digit     
   // calling to the function 
   n = minimumNumber(n, d);    
   cout<<"The minimum number after adding the new digit is "<<n<<endl;
   return 0;
}

Sortie

The minimum number after adding the new digit is -3124

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*N), où N est le nombre de chiffres dans le nombre donné.

La complexité spatiale du code ci-dessus est O(N), où N est le nombre de chiffres dans le nombre donné.

Méthode efficace

Dans la méthode précédente, nous avons vérifié chaque nombre, trouvé le premier nombre supérieur au nombre donné, puis l'avons ajouté et renvoyé lui-même, ce qui est une méthode efficace. Pour les nombres négatifs, trouvez le plus petit nombre, ajoutez-le et renvoyez-le.

Voyons le code−

Exemple

Exemple

#include <bits/stdc++.h>
using namespace std;
int findMin(string str, int d){
   // traversing over the string 
   for(int i=0; i<= str.size(); i++){
      if(str[i]-'0' > d){
         return stoi(str.substr(0,i) + to_string(d) + str.substr(i));
      }
   }
   return stoi(str + to_string(d));
}
int findMax(string str, int d){
   // traversing over the string 
   for(int i=0; i<= str.size(); i++){
      if(str[i]-'0' < d){
         return stoi(str.substr(0,i) + to_string(d) + str.substr(i));
      }
   }
   return stoi(str + to_string(d));
}
int minimumNumber(int n, int d){
   // checking for the negative number 
   int isNeg = 1;
   if(n < 0){
      n *= -1;
      isNeg = -1;
   }   
   // converting the current number to string 
   string str = to_string(n);    
   if(isNeg == 1){
      return findMin(str,d);
   }
   else{
      return -1*findMax(str,d);
   }
}
int main(){
   int n = 124; // given number 
   int d = 3; // given digit     
   // calling to the function 
   n = minimumNumber(n, d);    
   cout<<"The minimum number after adding the new digit is "<<n<<endl;
   return 0;
}

Sortie

The minimum number after adding the new digit is 1234

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N), où N est le nombre de chiffres du nombre donné.

La complexité spatiale du code ci-dessus est O(N), où N est le nombre de chiffres dans le nombre donné.

Conclusion

Dans ce tutoriel, nous avons implémenté une méthode pour insérer des nombres dans un nombre donné, c'est-à-dire ajouter un nouveau nombre donné avant, après ou entre les nombres. Nous avons vu deux méthodes, l'une avec une complexité temporelle de O(N*N) et l'autre avec une complexité temporelle de O(N). La complexité spatiale des deux méthodes est O(N).

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!