Finden Sie die kleinste Zahl, die durch Einfügen der angegebenen Zahlen gebildet wird

Das Einfügen einer Zahl in eine gegebene Zahl bedeutet das Hinzufügen einer neuen Zahl zu der gegebenen Zahl, entweder vor, nach oder in der Mitte der Zahl. Uns wurde eine Zahl und eine Zahl gegeben und wir müssen diese Zahl so klein wie möglich zur Zahl addieren. Um den Einfügevorgang zu erleichtern, wandeln wir die Zahl in eine Zeichenfolge um. Darüber hinaus kann die angegebene Zahl auch negativ sein, daher müssen wir diesen Fall berücksichtigen.

Beispiel Beispiel

Die chinesische Übersetzung von

Input1

lautet:

Input 1

Given number: 124
Given digit: 3
Output: 1234 

Erklärung − Wir haben vier Stellen, an denen wir die angegebene Zahl addieren können und das Ergebnis kann 3124, 1324, 1234, 1243 sein. Von den vieren ist der vorletzte der kleinste.

Die chinesische Übersetzung von

Input2

lautet:

Input 2

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

Erklärung − Wir haben vier Stellen, an denen wir die angegebene Zahl addieren können und das Ergebnis kann -3124, -1324, -1234, -1243 sein. Von den vieren ist der erste der kleinste.

Die chinesische Übersetzung von „Naiver Ansatz“ lautet: „Naiver Ansatz“.

Da wir nun das Beispiel gesehen haben, schauen wir uns die Schritte an, die wir durchführen werden, um das Problem zu lösen -

Zuerst prüfen wir, ob die aktuelle Zahl positiv oder negativ ist.

• Wenn die aktuelle Zahl negativ ist, markieren wir sie als negative Variable und machen die aktuelle Zahl positiv.

• Danach wandeln wir die aktuelle Zahl in eine Zeichenfolge um und rufen die Funktion basierend darauf auf, ob die aktuelle Zahl positiv oder negativ ist.

• In diesen Funktionen werden wir versuchen, die Zahl an jeder Position anzupassen und anhand positiver oder negativer Zahlen zu prüfen, ob die aktuelle Zahl kleiner oder größer ist.

• Wenn die aktuelle Zahl positiv ist, werden wir versuchen, die kleinste Zahl zu finden und zurückzugeben.

• Andernfalls ermitteln wir die größte Zahl und geben sie durch Multiplikation mit -1 zurück.

• Die chinesische Übersetzung von

  Beispiel

  lautet:
Beispiel

#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;
}

Ausgabe

The minimum number after adding the new digit is -3124

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N*N), wobei N die Anzahl der Ziffern in der gegebenen Zahl ist.

Die räumliche Komplexität des obigen Codes beträgt O(N), wobei N die Anzahl der Ziffern in der gegebenen Zahl ist.

Effiziente Methode

Bei der vorherigen Methode haben wir jede Zahl überprüft, die erste Zahl gefunden, die größer als die angegebene Zahl ist, sie dann addiert und sich selbst zurückgegeben, was eine effiziente Methode ist. Suchen Sie bei negativen Zahlen die kleinere Zahl, addieren Sie sie und geben Sie sie zurück.

Sehen wir uns den Code an−

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#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;
}

Ausgabe

The minimum number after adding the new digit is 1234

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), wobei N die Anzahl der Ziffern in der gegebenen Zahl ist.

Die räumliche Komplexität des obigen Codes beträgt O(N), wobei N die Anzahl der Ziffern in der gegebenen Zahl ist.

Fazit

In diesem Tutorial haben wir eine Methode implementiert, um Zahlen in eine bestimmte Zahl einzufügen, d. h. eine neue gegebene Zahl vor, nach oder zwischen den Zahlen hinzuzufügen. Wir haben zwei Methoden gesehen, eine mit der Zeitkomplexität O(N*N) und die andere mit der Zeitkomplexität O(N). Die räumliche Komplexität beider Methoden beträgt O(N).

Das obige ist der detaillierte Inhalt vonFinden Sie die kleinste Zahl, die durch Einfügen der angegebenen Zahlen gebildet wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!