Created
July 5, 2017 09:33
-
-
Save court-jus/0477ed96df26d426dc110794bb29f006 to your computer and use it in GitHub Desktop.
Get next bigger number using the same digits
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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