Form the smallest possible number from the given number

An algorithm to create the smallest possible number from the given number.

Example

Input:
55010
7652634

Output:
10055
2345667

We are going to use two different approaches to solve this problem. Everything will be written in ES6.

• In the first approach we will assume that provided number is in string format and solve it using sorting which will take O(nlogn).
• In Second approach we will solve with numeric value with O(d) time. Where d is the no of digits

Using sorting O(nlogn).

Implementation

• We will convert the number to character array and then sort the array.
• After sorting we will check if first character in array is 0.
• If it is not 0 then we will join the array and return it.
• If it is 0 then we will find the first non-zero number and swap it with 0 and return it.

function smallestPossibleNumber(num){
  //Create a character array and sort it
  let sorted = num.split('').sort();
  
  //Check if first character is not 0 then join and return it
  if(sorted[0] != '0'){
     return sorted.join('');
  }
  
  //find the index of the first non - zero character
  let index = 0;
  for(let i = 0; i < sorted.length; i++){
     if(sorted[i] > "0"){
       index = i;
       break;
     }
  }
  
  //Swap the indexes
  let temp = sorted[0];
  sorted[0] = sorted[index];
  sorted[index] = temp;
 
  //return the string after joining the characters of array
  return sorted.join('');
}

Input:
console.log(smallestPossibleNumber('55010'));
console.log(smallestPossibleNumber('7652634'));
console.log(smallestPossibleNumber('000001'));
console.log(smallestPossibleNumber('000000'));

Output:
10055
2345667
100000
000000
/*How it works
  let sorted = num.split('').sort(''); = ['5','5','0','1','0'].sort() = ['0','0','1','5','5']
  if(sorted[0] != '0'){   // '0' != '0' condition fails
     return sorted.join('');
  }
  
  //Find the index of the first non - zero character
  let index = 0;
  for(let i = 0; i < sorted.length; i++){
     if(sorted[i] > '0'){  // '1' > '0'
       index = i;      // index = 2;
       break;          // break;
     }
  }
  
  //swap the index
  var temp = sorted[0];      
  sorted[0] = sorted[index];
  sorted[index] = temp;
  
  //return the string
  return sorted.join('');
*/

Time Complexity: O(nlogn).
Space Complexity: O(n).

Time and Space complexity

• We are creating a character array which will take O(n) time and then sorting the array will take O(nlogn) after that we are finding the index which can take O(n) in worst case and joining the array to create the string will take O(n). As these all operations are running one after other, So Time complexity is O(n + nlogn + n + n) = O(nlogn).
• We are creating an array of characters from the string, So Space complexity is O(n).

Using numeric value O(logn) to form the smallest possible number.

Implementation

• We will create an array of numbers from 1 to 9.
• Then we will keep track of the digits present in the number by incrementing their count in the array.
• After that we will find the smallest non-zero digit and decrease its count by 1.
• In the end we will recreate the number by arranging them in ascending order and return the result.
• This solution is based on the counting sort.

function smallestPossibleNumber(num) { 
   // initialize frequency of each digit to Zero
   let freq = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; 
      
   // count frequency of each digit in the number
   while (num > 0){ 
     let d = parseInt(num % 10); // extract last digit
     freq[d]++; // increment counting
     num = parseInt(num / 10); //remove last digit
   } 

   // Set the LEFTMOST digit to minimum expect 0
   let result = 0; 
   for (let i = 1 ; i <= 9 ; i++) { 
      if (freq[i] != 0) { 
         result = i; 
         freq[i]--; 
         break;
      } 
   } 
       
   // arrange all remaining digits
   // in ascending order
   for (let i = 0 ; i <= 9 ; i++) {
      while (freq[i]-- != 0){ 
         result = result * 10 + i; 
      }
   }
      
  return result; 
} 

Input:
console.log(smallestPossibleNumber('55010'));
console.log(smallestPossibleNumber('7652634'));
console.log(smallestPossibleNumber('000001'));
console.log(smallestPossibleNumber('000000'));

Output:
10055
2345667
1
0
/* How it works
   // initialize frequency of each digit to Zero
   let freq = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
   
   // count frequency of each digit in the number
   while (num > 0){ 
     let d = parseInt(num % 10); // extract last digit
     freq[d]++; // increment counting        
     num = parseInt(num / 10); //remove last digit
   } 
   //After incrementing count
   //freq = [2, 1, 0, 0, 0, 2, 0, 0, 0, 0]
   
   // Set the LEFTMOST digit to minimum expect 0
   let result = 0; 
   for (let i = 1 ; i <= 9 ; i++) { 
      if (freq[i] != 0) { 
         result = i; 
         freq[i]--; 
         break;
      } 
   } 
   // result = 1
  
   // arrange all remaining digits
   // in ascending order
   for (let i = 0 ; i <= 9 ; i++) {
      while (freq[i]-- != 0){ 
         result = result * 10 + i; 
      }
   }

   //10
   //100
   //1005
   //10055
   //10055
   
   return result
*/

Time Complexity: O(logn).
Space Complexity: O(1).

Time and Space complexity

• We are removing each digit from the number and incrementing its respective count in an array that will take O(logn). Then we find the smallest non-zero number from the array in O(9). After that we are rearranging the digits to create the smallest number in O(9 * logn), so Time complexity is O(logn + 9 + 9logn) = O(logn) or O(d) where d is the no of digits.
• We are using constant space (an array of 9 numbers), so Space complexity is O(1).