CODEWITHSUNDEEP
algorithmmathdata-structures
deepesh17feb
deepesh17feb

Reputation: 87

Find the largest number small than having the same digits as of n

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

Upvotes: 2

Views: 1015

Answers (1)

user3386109
user3386109

Reputation: 34829

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.

Upvotes: 4

Related Questions