Q. The input of the problem is a number. (Say 43652). You have to compute a number using same digits such that new number is greater than original number and out of all such options, its should be closest to the original number. Answer for Example – 45236

A.

- Examine digits starting from zeroth place and move towards higher order. Stop at the point where current digit is less than previous one. Say this location is j. In example 4365, the digit is ‘3’.

- If no such element met and all digits occurred in ascending order, throw error saying that number is maximum possible with given digits.
- The digits examined so far (from 0th position to j-1) are sorted. Do binary search on same window and spot the element just greater than digit at location j. In example, its ‘5’.
- Swap these digits (Example: 45632)
- Examined digits (from 0th position to j-1) is still sorted. Change the order by reversing the sequence. (Example: sorted 45 ‘236’)
- The resulting number is the answer 🙂

Complexity O(n).

Spotting the element takes O(logn) as its binary search.

Sorting takes O(n) because we are just reversing the digits sequence.