Given a number, find the smallest number that has same set of digits as number and is greater than number.
Examples:
Input: 329876
Output: 362789
Input: 3689
Output: 3698
Input: 98732
Output: No possible sequence !!
-1
Input: n = 645987
Output: 647589
Approach:
1) If all digits sorted in descending order, then output is always “No possible sequence !!”.
Example: 98732.
2) If all digits are sorted in ascending order, then we need to swap last two digits only.
Example: 3689.
3) For other cases, we need to process the number from rightmost side because we need to find the smallest of all greater numbers
3.a) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit.
Example: If the input number is 645987, we will stop traversing at 5 as 5 is smaller than next digit i.e. 9. If we do not find such a digit, then output is “Not Possible”.
3.b) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’.
For 645987, the right side of 5 contains 987. The smallest digit greater than 5 is 7.
3.c) Swap the above found two digits, we get 647985 in above example.
3.d) Now sort all digits from position next to end of number in ascending order. For above input, we get 647589 which is the next greater number for input 645987 after sorting.
package com.geeks;
import java.util.Arrays;
public class NextBigInteger {
/**
* Get Next big integer.
* @param number
* @return return the next big integer.
*/
private static int getNextBigInt(int number) {
int length = (int) Math.ceil(Math.log10(number));
System.out.println(length);
int[] array = newint[length];
for (inti = 0; i < length; i++) {
array[length-i-1] = number%10;
number = number/10;
}
/** Find the index of smallest one from right to left. */
int index = -1;
for (inti = 0; i < length-1; i++) {
if(array[length-i-2]<array[length-i-1]) {
index = length-i-2;
break;
}
}
/** If no index found then greater number is no possible. */
if(index==-1) {
System.out.println("No possible sequence !!");
return -1;
}
int smallMaxIdx = index+1;
for (inti = index+2; i < length; i++) {
if(array[smallMaxIdx]>array[i]) {
smallMaxIdx = i;
}
}
int temp = array[index];
array[index] = array[smallMaxIdx];
array[smallMaxIdx] = temp;
Arrays.sort(array, index+1, length);
return integerArrayToInt(array);
}
/**
* Utilmethod to convert the int array to integer.
* @param array
* @return integer.
*/
private static int integerArrayToInt(int[] array) {
int len = array.length;
int number = array[len-1];
int factor = 10;
for (inti = 1; i < len; i++) {
number = number + factor * array[len-i-1];
factor = factor * 10;
}
return number;
}
/**
* Driver method.
* @param args
*/
public static void main(String[] args) {
int number = 645987;
int nextBigNumb = getNextBigInt(number);
System.out.println(nextBigNumb);
}
}
No comments:
Post a Comment