Skip to content

Instantly share code, notes, and snippets.

@ravichandrae
Created January 24, 2015 02:10
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 ravichandrae/72b2ccdf49ad9cb4ca16 to your computer and use it in GitHub Desktop.
Save ravichandrae/72b2ccdf49ad9cb4ca16 to your computer and use it in GitHub Desktop.
Given a number, how do we find the next greater number with the same digits?
num = raw_input()
ind = len(num)-1
while ind > 0 and num[ind] <= num[ind-1]:
ind -= 1
#There is no greater number with the same digits
if ind == 0:
print "Not possible"
else:
result = num[0:ind-1] #the left part
l_digit = num[ind-1] #left digit to be swapped
g_digit = num[ind] #candidate for digit to be swapped
right_digits = [num[ind]]
g_ind = ind+1
while g_ind < len(num):
right_digits.append(num[g_ind])
if num[g_ind] > l_digit and num[g_ind] < g_digit:
g_digit = num[g_ind]
g_ind += 1
result += g_digit
right_digits.remove(g_digit)
right_digits.append(l_digit)
right_digits.sort()
result += "".join(right_digits)
print result
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment