Inserting a number into a given number means adding a new number to the given number, either before, after or in the middle of the number. We have been given a number and a number and must add that number to the number in the smallest possible way. To facilitate the insertion operation, we will convert the number into a string. Furthermore, the given number can also be negative, so we have to account for this case.
Given number: 124 Given digit: 3 Output: 1234
Explanation − We have four places where we can add the given number and the result can be 3124, 1324, 1234, 1243. Of the four, the penultimate one is the smallest.
The Chinese translation ofGiven number: -124 Given digit: 3 Output: -3124
Explanation − We have four places where we can add the given number and the result can be -3124, -1324, -1234, -1243. Of the four, the first is the smallest.
The Chinese translation ofNow that we have seen the example, let's look at the steps we will perform to solve the problem -
First, we will check if the current number is positive or negative.
If the current number is negative, we will mark it as a negative variable and make the current number positive.
After that, we will convert the current number into a string and call the function basis based on the sign of the current number.
In these functions, we will try to fit the number at each position and check whether the current number is smaller or larger based on positive or negative numbers.
If the current number is positive, we will try to find the smallest number and return it.
Otherwise, we find the largest number and return it by multiplying by -1.
#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; }
The minimum number after adding the new digit is -3124
The time complexity of the above code is O(N*N), where N is the number of digits in the given number.
The space complexity of the above code is O(N), where N is the number of digits in the given number.
In the previous method, we have been checking each number, finding the first number that is greater than the given number, then adding it and returning itself, which is an efficient method. For negative numbers, find the smaller number, add it and return it.
Let’s look at the code−
The Chinese translation of#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; }
The minimum number after adding the new digit is 1234
The time complexity of the above code is O(N), where N is the number of digits in the given number.
The space complexity of the above code is O(N), where N is the number of digits in the given number.
In this tutorial, we implemented a method of inserting numbers into a given number, that is, adding a new given number before, after, or between numbers. We saw two methods, one with a time complexity of O(N*N) and the other with a time complexity of O(N). The space complexity of both methods is O(N).
The above is the detailed content of Find the smallest number formed by inserting the given numbers. For more information, please follow other related articles on the PHP Chinese website!