Find Next Larger no. Using Same Digits

Posted: September 12, 2012 in Amazon

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.

Advertisements
Comments
  1. Akhilesh Chaikam says:

    This website is very worthy .Thanks

  2. Harsh says:

    Thanks Akhilesh.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s