找出下一个更大的数

1. Introduction

In this article, we’re going to learn an algorithm to find the next higher number than a given non-negative number using the same set of digits.

In the case where the given number is already the highest possible number we can make with the given set of digits, the algorithm should return the given number itself.

2. Illustration

Let’s first understand the solution approach.

At first, we traverse the given number from the rightmost digit to find the first digit , which is smaller than the digit on its right. For example, If the given number is 12365, then the digit is 3 as 36.

In the case, when all the digits are higher than the digit on their right, such as in 4321, we return the given number itself as it is the highest possible number with the given set of digits.

Once the digit is found, we find the smallest digit on the right side of such that is greater than . In our example, the digit is 5 since 5<6 and 5>3.

Next, we swap the digits and in the given number. In our example, the digits 3 and 5 are swapped in 12365 and we get 12563.

Lastly, we reverse the sequence of digits after the digit to get the next higher number. In our example, the sequence 63 is reversed in 12563, and we get 12536, which is the next higher number than the given number 12365.

3. Algorithm

Let’s take a look at the pseudocode of the above-discussed algorithm:

algorithm findNextHigherNumber(str, n):
    // INPUT
    //   str = The string of the given number
    //   n = The length of the string
    // OUTPUT
    //   str = The string of the next higher number

    for i <- n - 1 to 1:
        if str[i] > str[i - 1]:
            break

    if str[i] > str[i - 1]:
        D <- str[i - 1]
        S <- str[i]
        for j <- i + 1 to n - 1:
            if str[j] > D and str[j] < S:
                S <- str[j]
        
        Swap the digits S and D
        Reverse the sequence of digits after the digit S
        return str
    else:
        return str

4. Time Complexity

Let’s assume that denotes the number of digits of the given number.

Then, each of the first and the second steps of the algorithm takes () time to find the required digits using a linear search.

The third step consumes () time to perform the swap operation. The fourth step takes () time to reverse the sequence of digits.

Thus, the overall time complexity of the above algorithm is ().

5. Conclusion

In this article, we’ve first learned an algorithm to find the next higher number than a given non-negative number using the same set of digits. Next, we analyzed the time complexity of the discussed algorithm.