Find the smallest number formed by inserting the given numbers

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.

ExampleExample

Input1

Input1

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.

Input2

Input2

Given 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.

Naive Approach

Naive Approach

Now 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.

Example

Example

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

Output

The minimum number after adding the new digit is -3124

Time and space complexity

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.

Efficient method

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−

Example

Example

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

Output

The minimum number after adding the new digit is 1234

Time and space complexity

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 conclusion

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!