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