## Saturday, January 30, 2016

### Find Next Greater Number Using Given Set Of Digits - Algorithms and Problem SolvingAlgorithms and Problem Solving

Find Next Greater Number Using Given Set Of Digits - Algorithms and Problem SolvingAlgorithms and Problem Solving
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.
```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){
n/=10;
}

//reverse to get the digits in MSB to LSB order
Collections.reverse(nums);

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
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){
}

//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)
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);
}
}
}```

Read full article from Find Next Greater Number Using Given Set Of Digits - Algorithms and Problem SolvingAlgorithms and Problem Solving