# Programming Interview Questions 24: Find Next Higher Number With Same Digits

Given a number, find the next higher number using only the digits in the given number. For example if the given number is 1234, next higher number with same digits is 1243.

The naive approach is to generate the numbers with all digit permutations and sort them. Then find the given number in the sorted sequence and return the next number in sorted order as a result. The complexity of this approach is pretty high though, because of the permutation step involved. A given number N has logN+1 digits, so there are O(logN!) permutations. After generating the permutations, sorting them will require O(logN!loglogN!) operations. We can simplify this further, remember that O(logN!) is equivalent to O(NlogN). And O(loglogN!) is O(logN). So, the complexity is O(N(logN)^2).

Let’s visualize a better solution using an example, the given number is 12543 and the resulting next higher number should be 13245. We scan the digits of the given number starting from the tenths digit (which is 4 in our case) going towards left. At each iteration we check the right digit of the current digit we’re at, and if the value of right is greater than current we stop, otherwise we continue to left. So we start with current digit 4, right digit is 3, and 4>=3 so we continue. Now current digit is 5, right digit is 4, and 5>= 4, continue. Now current is 2, right is 5, but it’s not 2>=5, so we stop. The digit 2 is our pivot digit. From the digits to the right of 2, we find the smallest digit higher than 2, which is 3. This part is important, we should find the smallest higher digit for the resulting number to be precisely the next higher than original number. We swap this digit and the pivot digit, so the number becomes 13542. Pivot digit is now 3. We sort all the digits to the right of the pivot digit in increasing order, resulting in 13245. This is it, here’s the code:

```def nextHigher(num): strNum=str(num) length=len(strNum) for i in range(length-2, -1, -1): current=strNum[i] right=strNum[i+1] if current<right: temp=sorted(strNum[i:]) next=temp[temp.index(current)+1] temp.remove(next) temp=''.join(temp) return int(strNum[:i]+next+temp) return num```

Note that if the digits of the given number is monotonically increasing from right to left, like 43221 then we won’t perform any operations, which is what we want because this is the highest number obtainable from these digits. There’s no higher number, so we return the given number itself. The same case occurs when the number has only a single digit, like 7. We can’t form a different number since there’s only a single digit.

The complexity of this algorithm also depends on the number of digits, and the sorting part dominates. A given number N has logN+1 digits and in the worst case we’ll have to sort logN digits. Which happens when all digits are increasing from right to left except the leftmost digit, for example 1987. For sorting we don’t have to use comparison based algorithms such as quicksort, mergesort, or heapsort which are O(KlogK), where K is the number of elements to sort. Since we know that digits are always between 0 and 9, we can use counting sort, radix sort, or bucket sort which can work in linear time O(K). So the overall complexity of sorting logN digits will stay linear resulting in overall complexity O(logN). Which is optimal since we have to check each digit at least once.

VN:F [1.9.22_1171]
Programming Interview Questions 24: Find Next Higher Number With Same Digits, 8.8 out of 10 based on 46 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
• Kowshik

In the third paragraph, theres a typo:
“At each iteration we check the right digit of the current digit we’re at, and if the value of right is LESS than current we stop, otherwise we continue to left.”

I think the correct version is:
“if the value of right is GREATER than current we stop, otherwise we continue to left.”

• Arden

Yes you’re right, updated the article. Thanks a lot for the notice.

• vaibhav goyal

Hi Arden,
There is a huge flaw, the number n has (log n) digits and hence there are (log n)! permutations O((log n)!) is not equal to O(n log n), infact much less; for example the number take a five digit number, number of permutations possible are only 5! and we can use some other sort like radix sort which here would take much less time.
Thanks

• sangeeta

Nice algo.. thanks for sharing :)

• Sandipan

We sort all the digits to the right of the pivot digit in increasing order, resulting in 13245.

We can also reverse the elements from the point we place the next highest or equal number with the current number!! Then we can avoid sorting.

Time complexity would be O(n)
Correct me if i am wrong!

• Arden

Yes you’re right, reversing the digits to the right of the pivot would also work. Yes you’re right, thanks a lot for realizing. But you should also be careful about swapping, for example if the original number is 136442. We’ll swap the pivot 3 with 4, and which 4 we swap with is important if we’re going to reverse later. We should swap with the rightmost one, otherwise we won’t get the next higher number.

Also note that complexity with sorting is still O(n), since we can use linear time sorting algorithms in this case (counting/radix/bucket sort). Because we know that digits are always in the range [0, 9].

Thanks for pointing out an alternative approach though, it’s an effective solution.

• Sangeeta

Great ! :)

Terse, comprehensive and exact description of the algorithm. Thanks for that.

Hi,
Whatif the numbers like 9999,10000???
Thanks.

• Sandipan

Since we are search for right to left for a digit which is less than the letter one.
i.e. arr[i] < arr[i+1]
Here the index goes lesser than 0 – it indicates that it is the greater element – no greater element can be found with same digits.

• Arden

I mention this case right after the code:
“Note that if the digits of the given number is monotonically increasing from right to left, like 43221 then we won’t perform any operations, which is what we want because this is the highest number obtainable from these digits. There’s no higher number, so we return the given number itself.”

Digits of both 9999 and 10000 are monotonically increasing from right to left.

Thank you…

You could also do a slight modification. As soon as the pivot index is found, sort the array from pividx+1 to the end, and swap the pividx element with the pividx+1.

• Dilip

But you can’t just swap pivot element and pivdx+1 element in all cases.
Say the input is 13621. The pivot is 3. After sorting, it becomes 13126. So in this case we have to swap pivot with 6. The moral is you have to traverse through the list to find out the smallest no, greater than the pivot.
We can do binary search to find swap element.
Correct me if i’m wrong

Nice logic .. Well explained ..

• arpita

really nice algo..thnks a lot

• bpin

A C++ STL algorithm: next_permutation is able to achieve the same goal in its implementation. Some explanation in this blog: http://wordaligned.org/articles/next-permutation

• Anonymous

Nice algorithm. Thanks.
But it seems there is a small bug in the code. If there is a duplicated digit and that digit is pivot as in 23431. The code returns 23134 which is less than the input since temp array has duplicated 3 consecutively and next=temp[temp.index(current)+1] selects second one where it is supposed to return “4” . To fix it, next should be chosen as the smallest larger digit in temp array rather than next digit after pivot

• rahul

you are awesome Arden..very nice collection with great explanation

• Kunal Kantawala

1232 will return 1223 with current approach.

• K. Skyy

Yeah, looks like the problem is that the code as is does not account for duplicate digits in the number. Changing the line “next=temp[temp.index(current)+1]” to “next = temp[i+1]” seems to do the trick.

• Debosmit Ray

That will solve the duplicate case. But, break the unique case.

• Debosmit Ray

The solution would be a little more subtle. Instead of including the pivot in the sorting process, we sort everything to the right of the pivot. An example of this would be, if the number is 136442, pivot is at 3 [index 1].
On sorting everything to the right of 3, we end up with [2,4,4,6]. We traverse this array to find the first number that is bigger than 3(pivotValue). This number is the first 4. We swap the 3 and this 4. Then, our sorted array looks like [2,3,4,6], and the first part of the string is “14”. On appending, we have 142346 which is the next biggest number. This handles both the unique and duplicate cases.

Some examples,
Num: 12543
Next_Higher_Number_With_Same_Digits: 13245

Num: 13542
Next_Higher_Number_With_Same_Digits: 14235

Num: 136442
Next_Higher_Number_With_Same_Digits: 142346

Num: 1232
Next_Higher_Number_With_Same_Digits: 1322

The owner of the blog has taken significant effort to create such a repository. Please refrain from tarnishing it by posting ‘improvement code’ that isn’t well tested.

• Yogo

Shouldn’t the complexity of the algorithm be O(n)? The ‘n’ term refers to the input size, not the quantity of the number. The input size is logarithmic with respect to the number being passed. Since we look at each digit, it’s O(n).

• Wellwisher
• anil kumar chaudhary

Its failing for array 1321.can we do something that includes duplicate elements also.??

• Amit Gaur
• Gregg Leventhal

def nextnum(num):
strnum=str(num)
m = max(strnum)
combos = []
n = min(strnum)
for i in range(int(str(n) * len(strnum)), int(str(m) * len(strnum)) + 1):
if sorted(str(i)) == sorted(strnum):
combos.append(i)
print combos
nexthighest = combos.index(num) + 1
print “%d is the next highest number” % combos[nexthighest]

Comments don’t save indenting? Oh well. This is a little brute force attempt, but it only uses a range of min * len(num), max * len(num) That should shave off something.

• crazykani

Wow. Your way of explaining solutions just blows my mind. Thanks a lot. It actually encourages me to learn and more importantly think.

• Raphael

O(log(n)) algorithm in C/C++.

// O(log(n))
int next_higher_number_same_digits(int x){
int n = int(log10(x)) + 1;

if(n<=1) return x;

int num = x/10, d = x%10;
int i;

// scan digits from right to left
// and stop when it finds the point
// where the digits stop increasing
for(i = 10; i = d; i*=10 ){
d = num%10;
num /= 10;
}

if(i > x)
return x;

d = num%10;
num /= 10;

int num1 = x, d1;
int m = 10, mj = 1, j;

// scan digits from right to left
// util it find the smallest digit
// bigger than d
for(j=1; j != i; j *=10){
d1 = num1%10;
num1 /= 10;
if(d1 > d && m > d1){
m = d1;
mj = j;
}
}

// swap d with m
x = x – d*i – m*mj + d*mj + m*i;

// everything on right of i-th position
// is in decreasing order (left to right)
// we must invert it. Then we are done!
num = x%i;
j=1; i /= 10;
while(j < i){
m = num%10;
d = num/(i/j);

x += – d*i – m*j + d*j + m*i;

num %= (i/j);
num /= 10;
i /= 10;
j*= 10;
}

return x;
}

• Patrick Sanan

Minor typo: “tenths digit” would be clearer as “tens digit” (a tenth being 0.1)

• Himanshu Kandwal

We can also make use of Knuth L algorithm which always generate lexicographically increasing sequence (only one Iteration).

• Sven Nebel

The Article is awesome, and the algorithm explanation works, however the implementation is missing to find the highest number greater than the pivot number, making the function report incorrect values like with nextHigher(319014690630) != 319014690036, the correct result should be 319014693006, find my working code here

“`
def nextHigher(num):
strNum=str(num)
length=len(strNum)
for i in range(length-2, -1, -1):
current=strNum[i]
right=strNum[i+1]
if current current)
index_of_slowest_number_higher_than_current = right_list.index(slowest_number_higher_than_current)
right_list[index_of_slowest_number_higher_than_current] = current
pivot[0] = slowest_number_higher_than_current
return int(”.join(left_list + pivot + sorted(right_list)))
return num
“`

• Rajat Vijay Bajaj

Just dropping one example: 6672727181 doesn’t work.
And there can be many more.

In case someone needs a better code: https://repl.it/LOZ6/2