Search the next highest number with same set of digits
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (3487)

You are given an integer number. How will you find the next higher number which has the exact same set of digits as the original number? i.e , 14739642 will result 14742369 .

Posted Answers

  • Split the sequence of digits in two parts so that the second part is in decreasing order as long as possible.
  • Take the last digit of the first part. Swap it with the smallest digit in the second part bigger than it.
  • Sort the second part in ascending order.
  • Merge the two parts and return the merged number.

Example - Let the input number be 14739642 .

Time to split the number in the worst case is \( O(n) \). It requires linear time for swapping to find the correct position. Sorting requires \( O(n) \) time for reversing.
\( \therefore \) Overall Running time = \( O(n) \).

You need to Sign In to post your solution.