Interesting, How to find next greater number with same digits

 

Given a number N, find the smallest number that has same set of digits as N and is greater than N. If theres no number greater than N by same same set of digits then print -1.
For example if N = 354 then all possible cobinations of the N digits will be 345, 435, 453, 534, 543. So the output will be 435 is the next smallest of all combinations and greater than N.

Find next greater number with same set of digits

Few examples:

N = 354
Output: 435

N = 218765
Output: 251678

N = 1234
Output: 1243

N = 4321
Output: -1

N = 534976
Output: 536479

Below code a simple permutation and combination of all digits from given N and get the next number from given number. If don't find any number then return -1.
For permutation and combination we use recursive algorithm and stores the combination in the TreeSet. 


import java.util.TreeSet;

public class HighestNumber {

 private TreeSet<Integer> combination = new TreeSet<Integer>();

 public static void main(String[] args) {

  Integer n = 354;
  HighestNumber obj = new HighestNumber();
  int nxtNumber = obj.findNextHighest(n);
  System.out.println(nxtNumber);
 }

 private int findNextHighest(int n) {
  permutation("", Integer.toString(n));
  return getNextHighestNumber(n);
 }

 /*
  * Recursive method to get all combination of digits
  */
 private void permutation(String prefix, String str) {
  int len = str.length();
  if (len == 0) {
   combination.add(Integer.valueOf(prefix));
  } else {
   for (int i = 0; i < len; i++) {

    String p = prefix + str.charAt(i);
    String s = str.substring(0, i) + str.substring(i + 1, len);
    permutation(p, s);
   }
  }
 }

 /*
  * Get the next number from combination collection TreeSet
  */
 private int getNextHighestNumber(int n) {
  boolean flag = false;
  int nxtNumber = -1;
  for (Integer num : combination) {
   if (num == n)
    flag = true;
   else if (flag) {
    nxtNumber = num;
    break;
   }
  }
  return nxtNumber;
 }
}

OUTPUT:


435

No comments:
Write comments