Skip to content

Instantly share code, notes, and snippets.

@court-jus
Created July 5, 2017 09:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save court-jus/0477ed96df26d426dc110794bb29f006 to your computer and use it in GitHub Desktop.
Save court-jus/0477ed96df26d426dc110794bb29f006 to your computer and use it in GitHub Desktop.
Get next bigger number using the same digits
def next_bigger(m):
# Firtst convert the int to a list of digits.
m = map(int, str(m))
# Call the main function.
nxt = _next_bigger(m)
if nxt == -1:
return -1
# Convert this list of digits to an int.
nxt = int("".join(map(str, nxt)))
return nxt
def _next_bigger(m):
# Get a list of digits and find the next bigger number using
# the same digits.
# Start with the first digit
first = m.pop(0)
#
# If the remaining digits are sorted, it means we already have
# the biggest number with this first digit, we have to step it
# up.
#
# Otherwise, we keep the first digit and repeat this process with
# the next one (hence the recursivity).
#
if sorted(m, reverse=True) == m:
# Step up first digit
# Get the next digit (the smaller one that is higher)
nfirst = sorted(filter(lambda d: d > first, m))
# If no other digit is higher than the first one, there's
# no solution, this number is already the highest one using
# its digits.
if not nfirst:
return -1
# The next first digit will be the smaller one (the list is sorted)
nfirst = nfirst[0]
# We take it from the list of digits but put the "previous" first one
# back in the list
m.remove(nfirst)
m.append(first)
return [nfirst] + sorted(m)
else:
# Keep same first digit and recursively call the function with the reduced
# list of digits.
recurse = _next_bigger(m)
if recurse == -1:
return -1
return [first] + recurse
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment