Tuesday, February 10, 2015

Given a number, using the same set of digits of it to compose the smallest number which is greater than the input

Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”. 

examples:
input: 1111
output: not possible

inout: 1234
output: 1243

input: 12345765
output: 12346557


In order to make a number greater but as small as possible, we need to achieve couple things: 1) try to change the least significant digits as possible; 2) in order make number bigger, we need to swap a smaller digit with a bigger digit on its right; 3) once we accomplish goal 1 and 2, we need to further make the number smaller. 

Here is the algorithm:
1. going from the right side of the number, find the first digit with index i which is smaller than the digit on its right
2. do binary search from i+1 to number.length-1 to find the smallest digit which is bigger than the digit at index i.
3. swap digits at index i and digit find in step 2.
3. reverse all of the digits from i+1 to number.length-1.


//digits are sorted descending numbers
public static int binarySearch(int[] digits, int start, int end, int v){
    while(start<end-1){
        int mid = (start+end)>>>1;
        if(digits[mid]>=v)
            start = mid;
        else
            end = mid;  
    }
    return digits[end] > v? end : start;
}

public static int swap(int[] digits, int t1, int t2){
  int d = digits[t1]; digits[t1] = digits[t2]; digits[t2] = d;
}

public static void reverse(int[] digits, int start, int end){
  while(start<end)
      swap(digits, start++, end--);
}

public static void findNGE(int number){
 int len = 0, temp = number;
 while(temp>0){
     len++;  temp = temp/10;
 }
 int[] digits = new int[len];
 temp = number;
 while(temp>0){
     digits[--len] = temp%10; temp = temp/10;
 }

 int end = digits.length - 1;
 while(end-1>=0 && digits[end]<=digits[end-1])
     end--;

 if(end==0)
   System.out.println("not possible");
 else{
   //binary search from end and digits.length -1
   //to find the smallest digit larger than digits[end-1]
   int target = binarySearch(digits, end, digits.length-1);
   swap(digits, target, end-1);
   reverse(digits, end, digits.length-1);
 
   int result = 0;
   for(int d : digits)
       result = d + result*10;

   System.out.println(result);
 }
}

1 comment:

  1. There is another similar problem: Given digit[] D, and a number A. Find the smallest number which is larger than A, and is consisted by the digit in D.

    For example:
    D = [0, 1, 8, 3], A = 8821. Result: 8830
    D = [0, 1, 8, 3], A = 8310. Result: 8311
    D = [0, 1, 8, 3], A = 12345. Result: 13000

    ReplyDelete