Form the smallest number using at most one swap operation
Given a non-negative number num. The problem is to apply at most one swap operation on the number num so that the resultant is the smallest possible number. The number could be very large so a string type can be used to store the number. The input does not contain leading 0’s and the output should also not contain leading 0’s.
Note: The same set of digits should be there in the resultant number as was there in the original number.
Examples:
Input : n = 9625635 Output : 2695635 Swapped the digits 9 and 2. Input : n = 1205763 Output : 1025763
Approach:
- Create an array rightMin[].
- rightMin[i] contains the index of the smallest digit which is on the right side of num[i] and also smaller than num[i].
- If no such digit exists then rightMin[i] = -1. Now, check that whether num[0] has a right smaller digit which is not equal to 0.
- If so then swap 1st digit with its right smaller digit. Else, traverse the rightMin[] array from i = 1 to n-1(where n is the total number of digits in num), and find the first element having rightMin[i] != -1.
- Perform the swap(num[i], num[rightMin[i]]) operation and break.
Implementation:
C++
// C++ implementation to form the smallest // number using at most one swap operation #include <bits/stdc++.h> using namespace std; // function to form the smallest number // using at most one swap operation string smallestNumber(string num) { int n = num.size(); int rightMin[n], right; // for the rightmost digit, there // will be no smaller right digit rightMin[n - 1] = -1; // index of the smallest right digit // till the current index from the // right direction right = n - 1; // traverse the array from second // right element up to the left // element for ( int i = n - 2; i >= 1; i--) { // if 'num[i]' is greater than // the smallest digit encountered // so far if (num[i] >= num[right]) rightMin[i] = right; else { // for cases like 120000654 or 1000000321 // rightMin will be same for all 0's // except the first from last if (num[i] == num[i + 1]) { rightMin[i] = right; } else { rightMin[i] = -1; right = i; } } } // special condition for the 1st digit so that // it is not swapped with digit '0' int small = -1; for ( int i = 1; i < n; i++) if (num[i] != '0' ) { if (small == -1) { if (num[i] < num[0]) small = i; } else if (num[i] <= num[small]) small = i; } if (small != -1) swap(num[0], num[small]); else { // traverse the 'rightMin[]' array from // 2nd digit up to the last digit for ( int i = 1; i < n; i++) { // if for the current digit, smaller // right digit exists, then swap it // with its smaller right digit and // break if (rightMin[i] != -1 && num[i] != num[rightMin[i]]) { // performing the required // swap operation swap(num[i], num[rightMin[i]]); break ; } } } // required smallest number return num; } // Driver program to test above int main() { string num = "9625635" ; cout << "Smallest number: " << smallestNumber(num); return 0; } |
Java
// Java implementation to form the smallest // number using at most one swap operation import java.util.*; import java.lang.*; public class w3wiki { // function to form the smallest number // using at most one swap operation public static String smallestNumber(String str) { char [] num = str.toCharArray(); int n = str.length(); int [] rightMin = new int [n]; // for the rightmost digit, there // will be no smaller right digit rightMin[n - 1 ] = - 1 ; // index of the smallest right digit // till the current index from the // right direction int right = n - 1 ; // traverse the array from second // right element up to the left // element for ( int i = n - 2 ; i >= 1 ; i--) { // if 'num[i]' is greater than // the smallest digit // encountered so far if (num[i] > num[right]) rightMin[i] = right; else { // there is no smaller right // digit for 'num[i]' rightMin[i] = - 1 ; // update 'right' index right = i; } } // special condition for the 1st // digit so that it is not swapped // with digit '0' int small = - 1 ; for ( int i = 1 ; i < n; i++) if (num[i] != '0' ) { if (small == - 1 ) { if (num[i] < num[ 0 ]) small = i; } else if (num[i] < num[small]) small = i; } if (small != - 1 ) { char temp; temp = num[ 0 ]; num[ 0 ] = num[small]; num[small] = temp; } else { // traverse the 'rightMin[]' // array from 2nd digit up // to the last digit for ( int i = 1 ; i < n; i++) { // if for the current digit, // smaller right digit exists, // then swap it with its smaller // right digit and break if (rightMin[i] != - 1 ) { // performing the required // swap operation char temp; temp = num[i]; num[i] = num[rightMin[i]]; num[rightMin[i]] = temp; break ; } } } // required smallest number return ( new String(num)); } // driver function public static void main(String argc[]) { String num = "9625635" ; System.out.println( "Smallest number: " + smallestNumber(num)); } } /*This code is contributed by Sagar Shukla.*/ |
Python 3
# Python implementation to form the smallest # number using at most one swap operation # function to form the smallest number # using at most one swap operation def smallestNumber(num): num = list (num) n = len (num) rightMin = [ 0 ] * n right = 0 # for the rightmost digit, there # will be no smaller right digit rightMin[n - 1 ] = - 1 ; # index of the smallest right digit # till the current index from the # right direction right = n - 1 ; # traverse the array from second # right element up to the left # element for i in range (n - 2 , 0 , - 1 ): # if 'num[i]' is greater than # the smallest digit encountered # so far if num[i] > num[right]: rightMin[i] = right else : # there is no smaller right # digit for 'num[i]' rightMin[i] = - 1 # update 'right' index right = i # special condition for the 1st digit so that # it is not swapped with digit '0' small = - 1 for i in range ( 1 , n): if num[i] ! = '0' : if small = = - 1 : if num[i] < num[ 0 ]: small = i elif num[i] < num[small]: small = i if small ! = - 1 : num[ 0 ], num[small] = num[small], num[ 0 ] else : # traverse the 'rightMin[]' array from # 2nd digit up to the last digit for i in range ( 1 , n): # if for the current digit, smaller # right digit exists, then swap it # with its smaller right digit and # break if rightMin[i] ! = - 1 : # performing the required # swap operation num[i], num[rightMin[i]] = num[rightMin[i]], num[i] break # required smallest number return ''.join(num) # Driver Code if __name__ = = "__main__" : num = "9625635" print ( "Smallest number: " , smallestNumber(num)) # This code is contributed by # sanjeev2552 |
C#
// C# implementation to form the smallest // number using at most one swap operation. using System; public class w3wiki { // function to form the smallest number // using at most one swap operation public static String smallestNumber(String str) { char [] num = str.ToCharArray(); int n = str.Length; int [] rightMin = new int [n]; // for the rightmost digit, there // will be no smaller right digit rightMin[n - 1] = -1; // index of the smallest right digit // till the current index from the // right direction int right = n - 1; // traverse the array from second // right element up to the left // element for ( int i = n - 2; i >= 1; i--) { // if 'num[i]' is greater than // the smallest digit // encountered so far if (num[i] > num[right]) rightMin[i] = right; else { // there is no smaller right // digit for 'num[i]' rightMin[i] = -1; // update 'right' index right = i; } } // special condition for the 1st // digit so that it is not swapped // with digit '0' int small = -1; for ( int i = 1; i < n; i++) if (num[i] != '0' ) { if (small == -1) { if (num[i] < num[0]) small = i; } else if (num[i] < num[small]) small = i; } if (small != -1) { char temp; temp = num[0]; num[0] = num[small]; num[small] = temp; } else { // traverse the 'rightMin[]' // array from 2nd digit up // to the last digit for ( int i = 1; i < n; i++) { // if for the current digit, // smaller right digit exists, // then swap it with its smaller // right digit and break if (rightMin[i] != -1) { // performing the required // swap operation char temp; temp = num[i]; num[i] = num[rightMin[i]]; num[rightMin[i]] = temp; break ; } } } // required smallest number return ( new String(num)); } // Driver code public static void Main() { String num = "9625635" ; Console.Write( "Smallest number: " + smallestNumber(num)); } } // This code is contributed by Nitin Mittal. |
PHP
Javascript
Output
Smallest number: 2695635
Time Complexity: O(n), where n is the total number of digits.
Auxiliary Space: O(n), where n is the total number of digits.