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]
Rating: 9.7/10 (30 votes cast)
Programming Interview Questions 24: Find Next Higher Number With Same Digits, 9.7 out of 10 based on 30 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 ! :)

  • Ashot Madatyan

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

  • Varadharajan

    Hi,
    Whatif the numbers like 9999,10000???
    Can you please tell me??
    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.

      • Varadharajan

        Thank you…

  • Ashot Madatyan

    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

  • Aravind Prasad

    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.

  • 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.??