# Find next highest number with the same digits

Question:

Given any integer, efficiently find the next highest integer that uses the same digits. For example if the number is 15432, you should return 21345.

Program: I have written a program which automatically generates a random number in the range random.randint(999, 999999):

print "Find the Next highest number!"
# Find the next highest digit which needs to be corrected.
# Two step approach.
#########
# Step1. Check all the digits expect the highest digit.
#        Whether that needs to be corrected.
#        If yes, place next higest digit and sort the remaning digits after the placed
#        digit.

#########
# Step2
# The highest digit needs to be changed.
# This occurs when all the remaning digit except the highest digit is in decending order
#  1. Shift rotate the number right by one digit. i.e. place the last digit  to the
#     hightest index and shift the current highest digit once place right.
#  2. sort the remaning digits in the acending order.
#  3. Join the digits in index 0 and 1 with the sorted list in step2
#  eg: 15432
#  1.  21543
#  2.  345
#  3.  21345

import sys
import random
number = random.randint(999,999999)
stringArr = str(number)
numberList = list(stringArr) # Given Number converted in list format
str_excpet_highest_digit = stringArr[1:]
array_excpet_highest_digit = list(str_excpet_highest_digit)
correct_Index = -1
correct_Digit = -1 # current digit what is moved from the existing index
digit_Moved = -1 # digit what is moved in to the correct index location
highestDigitChanged = -1

###### Functions #######
def swapDigitAtInidix(fromIndex,toIndex,array):
temp = array[fromIndex]
array[fromIndex] = array[toIndex]
array[toIndex] = temp
return array # end function

def sortRemainingList(startIndex,array):
sortedList = []
temp = []
for i in range(startIndex):
sortedList.append(array[i])
for j in range(startIndex,len(array)):
temp.append(array[j])

# sort the right part of the list
temp=sorted(temp)
convertToString1 = ''.join(sortedList)
convertToString2 = ''.join(temp)
sortedString = convertToString1 + convertToString2
sortedList = list(sortedString)
print "Number except the highest digit:",sortedList
return sortedList # end function

# This will check the highest digit to be replaced. Returns the updated number
def highestDigitTobeChanged(numberList):
highestDigit = numberList[0]
newHighestDigit = -1
# find the next highest number
for i in range(len(numberList)):
if highestDigit < numberList[i]:
numberList = swapDigitAtInidix(0,i,numberList)
strNUmber = ''.join(numberList)
strTemp = strNUmber[1:]
strSorted = ''.join(sorted(strTemp))
strNUmber = strNUmber[0] + strSorted
return strNUmber
##### All Fucntions Defined #####

###### Start ######
print "Given Number:", number

##### Step1 #####
print "List without highest digit:",array_excpet_highest_digit
for i in range(len(str_excpet_highest_digit)-1):
# Find the higest index.
if (array_excpet_highest_digit[i] < array_excpet_highest_digit[i+1]) and correct_Index == -1:
correct_Index = i
correct_Digit = array_excpet_highest_digit[i]
# swap the digit
array_excpet_highest_digit = swapDigitAtInidix(i,i+1,array_excpet_highest_digit)
digit_Moved = array_excpet_highest_digit[i]
print "MOdified List without higest digit",array_excpet_highest_digit
# To check whether the new moved digit is the next bigger digit
elif (correct_Index != -1 ) and ( correct_Digit < array_excpet_highest_digit[i] and digit_Moved > array_excpet_highest_digit[i] ):
array_excpet_highest_digit = swapDigitAtInidix(correct_Index,i,array_excpet_highest_digit)
digit_Moved = array_excpet_highest_digit[correct_Index]
print "MOdified List without higest digit",array_excpet_highest_digit

# To check whether the new moved digit is the next bigger digit. Apply this for the last element in the list
if (correct_Index != -1 ) and ( correct_Digit < array_excpet_highest_digit[i+1] and digit_Moved > array_excpet_highest_digit[i+1] ):
array_excpet_highest_digit = swapDigitAtInidix(correct_Index,i+1,array_excpet_highest_digit)
digit_Moved = array_excpet_highest_digit[correct_Index]
print "MOdified List without higest digit",array_excpet_highest_digit

##### Step2 #####
if correct_Index == -1:
# Except the highest digit all other digits in decending order. Which means Step1 needs to be done.
finalNumber = highestDigitTobeChanged(numberList)

else:
# Create the remaining sorted list
array_excpet_highest_digit = sortRemainingList(correct_Index+1,array_excpet_highest_digit)
tmpfinalString=''.join(array_excpet_highest_digit)
finalNumber = int(stringArr[0] + tmpfinalString)

print "Next Higest Number:",  finalNumber


Please let me know if there are any better solutions.

• This sounds like a programming contest question. Can you give a reference to the origin? Oct 19, 2014 at 14:44
• Google found this : thereq.com/q/151/technical-software-interview-question/… . Not sure if this is the original question. Oct 20, 2014 at 9:46

Your approach doesn't actually work; for example, for number = 217294 it gives the result as 221479 (what about 217429 or the other nine numbers between the two?)

Your code is not compliant with Python's style guide and documentation conventions, including the following:

1. import statements in the wrong order, not separated from the body of the code, and one isn't even used;
2. function and variable names not lowercase_with_underscores (or even consistent); and
3. block comments not in docstring form.

You could make much more use of function definitions; all that should run directly is something like the following, at the bottom of the script:

if __name__ == "__main__":

import random # isn't needed by any other functions

test = random.randint(999, 999999)
print "Input number: {0}".format(test)
result = find_next_highest(test)
print "Next highest number with same digits: {0}".format(result)


This allows you to import your functions elsewhere without having to run anything. It would also make testing your code much easier if more of it were inside functions.

• Could you tell me what is the correct way to name the functions, variables, modules etc.. in python ? Oct 20, 2014 at 9:46
• @python_lover that information is all in the style guide, to which I've provided a link in the answer Oct 20, 2014 at 9:48