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 = new
int[length];
for (int
i = 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 (int
i = 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 (int
i = 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);
}
/**
* Util
method 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 (int
i = 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