Question

How to find the smallest number greater than a given number, using the same digits in Python

Answer 1

# Time Complexity: O(n!)
# Generates all permutations of the digits
# Uses a lot of RAM

import itertools
 
def nextGreaterNumber(n):
    # Convert the number to a string so we can permute its digits
    s = str(n)

    # Generate all permutations of the digits.
    # Each permutation is a tuple of characters, so we join them and convert to int.
    # Using a set removes duplicates (important for numbers like 1122).
    listOfNumbers = set([int(''.join(s)) for s in itertools.permutations(s, len(s))])   
    
    print(listOfNumbers) # debug (remove)

    # Convert the set to a list and sort it in ascending order
    listOfNumbers = sorted(list(listOfNumbers))
    
    print(listOfNumbers)  # debug (remove)

    try:
        # Find the index of the original number and return the next one in the list
        return listOfNumbers[listOfNumbers.index(n) + 1]
    except Exception:
        # If n is the largest permutation, there is no next greater number
        return -1
 

print("Result:", nextGreaterNumber(53496))
print("---------------------------------")
print("Result:", nextGreaterNumber(111))   # -1 (all digits identical)
print("-------------------------------")
print("Result:", nextGreaterNumber(7600)) # -1 (already the largest)

 
 
'''
run:
     
{46593, 63495, 64539, 56349, 39456, 39465, 59436, 43569, 63549, 59463, 45639, 56394, 43596, 36945, 64593, 96345, 36954, 54369, 96354, 56934, 35946, 36459, 63594, 56943, 95346, 56439, 39546, 35964, 54396, 45693, 95364, 43659, 34956, 35469, 39564, 36495, 94356, 34965, 54936, 94365, 35496, 56493, 43695, 54963, 96435, 53946, 36549, 96453, 53964, 49356, 95436, 49365, 53469, 39645, 69345, 39654, 95463, 69354, 59634, 36594, 53496, 59643, 34569, 93456, 96534, 46359, 93465, 96543, 34596, 45369, 46395, 69435, 35649, 65349, 94536, 69453, 45396, 46935, 34659, 94563, 64359, 46953, 93546, 35694, 54639, 45936, 65394, 93564, 49536, 34695, 45963, 64395, 65934, 53649, 95634, 65943, 49563, 95643, 69534, 65439, 54693, 64935, 69543, 94635, 43956, 64953, 43965, 53694, 94653, 63945, 46539, 93645, 59346, 63954, 65493, 93654, 49635, 59364, 63459, 49653}
[34569, 34596, 34659, 34695, 34956, 34965, 35469, 35496, 35649, 35694, 35946, 35964, 36459, 36495, 36549, 36594, 36945, 36954, 39456, 39465, 39546, 39564, 39645, 39654, 43569, 43596, 43659, 43695, 43956, 43965, 45369, 45396, 45639, 45693, 45936, 45963, 46359, 46395, 46539, 46593, 46935, 46953, 49356, 49365, 49536, 49563, 49635, 49653, 53469, 53496, 53649, 53694, 53946, 53964, 54369, 54396, 54639, 54693, 54936, 54963, 56349, 56394, 56439, 56493, 56934, 56943, 59346, 59364, 59436, 59463, 59634, 59643, 63459, 63495, 63549, 63594, 63945, 63954, 64359, 64395, 64539, 64593, 64935, 64953, 65349, 65394, 65439, 65493, 65934, 65943, 69345, 69354, 69435, 69453, 69534, 69543, 93456, 93465, 93546, 93564, 93645, 93654, 94356, 94365, 94536, 94563, 94635, 94653, 95346, 95364, 95436, 95463, 95634, 95643, 96345, 96354, 96435, 96453, 96534, 96543]
Result: 53649
---------------------------------
{111}
[111]
Result: -1
-------------------------------
{706, 67, 670, 6700, 76, 7600, 7060, 6070, 6007, 760, 7006, 607}
[67, 76, 607, 670, 706, 760, 6007, 6070, 6700, 7006, 7060, 7600]
Result: -1

'''

 

70+ SQL courses for beginners and professionals

Answer 2

# Time Complexity: O(n)
# One pass from right to left
# One pass from right to left again
# One reverse of a suffix
# No heavy memory usage

def next_greater_number(n):
    # Convert the number to a list of its digits (as characters)
    digits = list(str(n))
    length = len(digits)
    
    # Step 1: Find the pivot — the first digit from the right
    # that is smaller than the digit immediately after it.
    # This identifies where the next permutation must change.
    for i in range(length - 2, -1, -1):
        if digits[i] < digits[i + 1]:
            break
    else:
        # If no pivot is found, the digits are in descending order.
        # That means no larger number can be formed.
        return -1

    print(digits[i]) # debug (remove)
    
    # Step 2: Find the smallest digit to the right of the pivot
    # that is larger than the pivot digit.
    # This ensures the next number is the *smallest possible* greater number.
    for j in range(length - 1, i, -1):
        if digits[j] > digits[i]:
            break

    print(digits[j]) # debug (remove)
    
    # Step 3: Swap the pivot with that next larger digit.
    digits[i], digits[j] = digits[j], digits[i]
    
    print(digits) # debug (remove)
    
    # Step 4: Reverse the suffix (everything to the right of the pivot).
    # This puts the remaining digits in ascending order,
    # ensuring the result is the next immediate permutation.
    digits[i + 1:] = reversed(digits[i + 1:])
    
    print(digits[i + 1:]) # debug (remove)

    # Convert the list of digits back into an integer.
    return int("".join(digits))


print("Result:", next_greater_number(53496))
print("---------------------------------")
print("Result:", next_greater_number(111))   # -1 (all digits identical)
print("-------------------------------")
print("Result:", next_greater_number(7600)) # -1 (already the largest)


'''
run:

4
6
['5', '3', '6', '9', '4']
['4', '9']
Result: 53649
---------------------------------
Result: -1
-------------------------------
Result: -1

'''

 

70+ SQL courses for beginners and professionals