Algorithms
Find Next Greater Number Using Given Set Of Digits
Given a set S of digits [0-9] and a number n. Find the smallest integer larger than n (ceiling) using only digits from the given set S. You can use a value as many times you want.
For example, d=[1, 2, 4, 8] and n=8753 then return 8811. For, d=[0, 1, 8, 3] and n=8821 then return 8830. For d=[0, 1, 8, 3] and n=8310 then return 8311.
As we know two numbers are equal when all their digits are same in respective positions. The smallest number greater than a number n must have at least one digit greater than its respective position and all the positions right to this position must contain the smallest digits possible.
For example, d=[0, 1, 8, 3] and n=8821 then as long as the digits match from MSB to LSB position we have the numbers matching. For example, [88]. If at a position we don’t find the digit in the given digit, for example 3 at position 2 of n, then we want to replace this with the next higher number from the digits d. The next higher digit in this case is 3. Once we find a higher digit we need to have the rest of the digits in the LSBs from this position as smallest as possible i.e. the smallest one. For example, in this case the rest of the position will be filled with smallest digit in d which is 0. So, final answer is 8830.
Question is how to get the next higher digit? We can simply sort the digit array and use binary search to get the floor (smallest number greater than or equal to key) from the array. However there is a special case when all the digits in the given number is contained in the digit. In this case we will end up in generating the input number itself as the next greater number (why?). How to solve this issue? If we do not find a higher digit in the whole scan then we need to replace the LSB of the number by the smallest digit that is strictly higher than the current digit at that position (why?).
The following is an O(nlgn) implementation of the above idea.
public static int[] nextHigherWithDigits(int[] digits, int n){
//get the target digits sorted
int[] sortedDigits = Arrays.copyOf(digits, digits.length);
Arrays.sort(sortedDigits);
//get the digits of the number from LSB to MSB oder
ArrayList<Integer> nums = new ArrayList<Integer>();
while(n>0){
nums.add(n%10);
n/=10;
}
//reverse to get the digits in MSB to LSB order
Collections.reverse(nums);
boolean higherAdded = false;
int[] res = new int[nums.size()];
int i = 0;
//for each digit in thr number find the next higher in the sorted target digits
for(int num : nums){
//if a higher digit was already found in previous step then rest of the digits should have the smallest digit
if(higherAdded){
//add the smallest digit
res[i++] = sortedDigits[0];
continue;
}
//otherwise , find the next higher (or equal) digit
int nextHigher = binarySearchCeiling(sortedDigits, 0, sortedDigits.length-1, num);
//if no such higher digit then no solution
if(nextHigher == -1){
return null;
}
//otherwise if the digit is indeed higher then all subsequent digits should be smallest, so mark this event
else if(sortedDigits[nextHigher] > num){
higherAdded = true;
}
//add the next higher (or equal digit)
res[i++] = sortedDigits[nextHigher];
}
//If we didn;t find any higher digit, which is only possible when we found all equal digits
//then set the LSB to the next strictly higher number (not equal)
if(!higherAdded){
int nextHigher = binarySearchCeiling(sortedDigits, 0, sortedDigits.length-1, res[i-1]+1);
if(nextHigher == -1){
return null;
}
res[i-1] = sortedDigits[nextHigher];
}
return res;
}
public static int binarySearchCeiling(int A[], int l, int h, int key){
int mid = (l+h)/2;
if(A[l] >= key){
return l;
}
if(A[h] < key ){
return -1;
}
if(A[mid] == key){
return mid;
}
//mid is greater than key, so either mid is the ceil or it exists in A[l..mid-1]
else if(A[mid] > key){
if(mid-1 >= l && A[mid-1] <= key){
return mid;
}
else{
return binarySearchCeiling(A, l, mid-1, key);
}
}
//mid is less than the key, so either mid+1 is the ceil or it exists in A[mid+1...h]
else{
if(mid + 1 <= h && A[mid+1] >= key){
return mid+1;
}
else{
return binarySearchCeiling(A, mid+1, h, key);
}
}
}