Question:
Given any integer, efficiently find the next highest integer that uses the same digits. For example if the number is
15432
, you should return21345
.
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
# Perform the following task
# 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.