Showing posts with label next greater number. Show all posts
Showing posts with label next greater number. Show all posts

## 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.

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