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);
}
}
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.
ReplyDeleteFor 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