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

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