Next Greater Number with Same Set of Digits in Java

A number (num) is given. The task is to find a number that is the smallest that comprises the same set of digits as num and must be larger than the number num. If the number num is the largest number possible with its digits set, then it is not possible to find the next greater number, and hence, a message should be displayed accordingly.

Example 1:

Input: 89321

Output: 91238

Explanation: Numbers that are made of the digits 1, 2, 3, 8, 9 and are larger than the number 89123 are:

98123, 98132, 98213, 98231, 98312, 98321, 93128, 93182, 93218, 93281, 93812, 93821, 92138, 92183, 92318, 92381, 92813, 92831, 91238, 91283, 91328, 91382, 91823, 91832

In all these number the smallest number is 91238.

Example 2:

Input: 3648

Output: 3684

Explanation: Numbers that are made of the digits 3, 8, 4, 6 and are larger than 3648 are:

3684, 4368, 4386, 4638, 4683, 4836, 4863, 6348, 6384, 6438, 6483, 6834, 6843, 8346, 8364, 8436, 8463, 8634, 8643

In all these number the smallest number is 3684.

Example 3:

Input: 9100

Output: It is not possible to find the next greater number.

Explanation: The largest number that is made of the digits 9, 1, 0, 0 is 9100. Thus, it is not possible to find a number that is greater than 9100 using the given digits.

Observation

The following are some of the important points of observation.

• If the digits of a number are being arranged in the descending order, then the result is "It is not possible to find the next greater number". For example, 98675.
• If the digits of a number are being arranged in the ascending order, then one needs to interchange the last two digits of the number. For example, for the number 4567, the next greater number is 4576.
• For the rest of the other cases, one needs to begin the processing of the number from the rightmost side as one has to find the smallest among the numbers that are larger than the given number.

Algorithm

The following is the algorithm for computing the next greater number on the basis of the observation described above.

Step 1: Traverse the number num from the rightmost digit, keep traversing till one finds a digit that is lesser than the last traversed digit. For example, if one takes the input number as "4975", one has to stop at 4. It is because 4 is lesser than the next digit, 9. If one does not get such a digit, then it is not possible to find the next greater number.

Step 2: Now start searching the right side of the above found digit 'd' for the smallest digit larger than 'd'. For the number 4975, the right side of 4 contains 975. Out of the digits 9, 7, and 5, the smallest digit larger than 4 is 5.

Step 3: Now, swap the numbers 4 and 5. Thus, one will get 5974. However, this number is not the smallest among the largest. Therefore, we need to sort the digits after digit 5. Thus, by sorting the digits of the number 5974, one will get 5479. The number 5479 is the smallest among the numbers that are greater than the number 4975 and comprising of the digits 4, 9, 7, 5.

Using Permutation

It is a brute force approach. In this approach, we will be computing each number that can be formed using the digits present in the given number num. We will be storing those computed numbers in a hash set hs. In that hash set, we will be picking a number that is minimum as well as greater than the number num.

FileName: NextGreaterNumber.java

Output:

For the number: 536479 The next greater number is: 536497 For the number: 654321 The next greater number is not possible. For the number: 4876 The next greater number is: 6478 

Complexity Analysis: In the above program, we have used backtracking to find the next greater number. Thus, the time complexity of the above program is exponential. Suppose the number num has d digits. Thus, the total numbers present in the hash set hs n!. Therefore, the space complexity of the above program is O(n!).

Using Sorting

FileName: NextGreaterNumber

Output:

For the number: 536479 The next greater number is: 536497 For the number: 654321 The next greater number is not possible. For the number: 4876 The next greater number is: 6478 

Complexity Analysis: In the above program, we have used loops as well as sorting. The loop takes O(n) time, and the sorting takes O(n * log(n)) time. Hence, the total time complexity of the program is O(n + n * log(n)), where n is the total number of digits present in the input number. As no extra space is used; therefore, the space complexity of the program is constant, i.e., O(1).

Note: We can even reduce the time complexity further. Note that instead of sorting, we can also use the inbuild reverse method to do the sorting. It is because the digits that we are sorting are arranged in descending order. For example, sorting 6, 5, 4, 3, 2, 1 should not take O(n x log(n)) time. Only reversing the order will do the job. So, instead of sorting, use the reverse() method to reduce the time complexity to O(n).

In the method isSwapPossible(), make the following changes to get the same result.