2

Given a number n, find the largest number small than having the same digits as of n. E.g. 231 output will be 213?

deepesh17feb
  • 87
  • 1
  • 1
  • 9
  • what happen if we have n = 444 or 1234? – Pham Trung Mar 05 '15 at 08:15
  • you might also be interested in smallest permutation greater then given one http://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string compare it with your problem :) almost the reverse of it – advocateofnone Mar 05 '15 at 08:26

1 Answers1

4

You need to find the last digit that has a smaller digit to its right, and swap that digit with the largest of the smaller digits to its right. And then sort all of the digits to the right of the swapped number in descending order.

For example, given 74125, 4 is the last digit that has smaller digits to the right, and 2 is the largest of the smaller digits so the answer is found by swapping 4 and 2 to get 72145, and then sort all of the digits to the right of the 2 to get 72541.

Additional note: If there are multiple copies of the largest-of-the-smaller-digits-to-the-right digit, then swap with the leftmost copy of that digit. So for example, 74122267 becomes 72142267 before sorting, and 72764221 after sorting.

user3386109
  • 34,287
  • 7
  • 49
  • 68
  • 2
    should it not be 72541? The numbers after the 2 should be in descending order – Dane I Mar 05 '15 at 08:15
  • 1
    @Dane Yup, thanks, I knew I was missing something, but couldn't remember what. – user3386109 Mar 05 '15 at 08:18
  • 1
    Need to handle special case like 2000. – hk6279 Mar 05 '15 at 11:59
  • @hk6279 True, I've added an additional note to the answer. The algorithm would turn 2000 into 0200, which may have to be treated as *"no valid answer exists"* similar to 444 and 1234 that PhamTrung mentioned. – user3386109 Mar 05 '15 at 20:20