Write a program to find the next highest number by rearranging the digits of a number. For instance,
If input is 13483 then output must be 13834.
Test cases:
Input Output
3971 7139
83971 87139
54321 54321
405321 410235
Logic:
Let take a numner 12543 and resulting next higher number is 13245.
Scan the digits from the tenths digit going towards left (which is 4 in our case)
At each iteration we check the right digit of the current digit we are at and if the value of the right is greater then current we stop other continue to left
4>3 continue
5>4 contine
2>5 stop
2 is our pivot element.
from the digit 2 to the right we find the smallest higher digit of resulting number 2 which 3.
swap the 3 with 2, it will become 13542. now 3 is our pivot element.
Now revere the number to right pivot element i.e 3 , it comes 13245 result.
Note : in case of repeating digit like 147553 we need to swap the 4 with the rightmost digit, otherwise we don't get the highest number.
Time complexity would be O(n)
Code :
If input is 13483 then output must be 13834.
Test cases:
Input Output
3971 7139
83971 87139
54321 54321
405321 410235
Logic:
Let take a numner 12543 and resulting next higher number is 13245.
Scan the digits from the tenths digit going towards left (which is 4 in our case)
At each iteration we check the right digit of the current digit we are at and if the value of the right is greater then current we stop other continue to left
4>3 continue
5>4 contine
2>5 stop
2 is our pivot element.
from the digit 2 to the right we find the smallest higher digit of resulting number 2 which 3.
swap the 3 with 2, it will become 13542. now 3 is our pivot element.
Now revere the number to right pivot element i.e 3 , it comes 13245 result.
Note : in case of repeating digit like 147553 we need to swap the 4 with the rightmost digit, otherwise we don't get the highest number.
Time complexity would be O(n)
Code :
If you know anyone who has started learning Java, why not help them out! Just share this post with them.
Thanks for studying today!...
Thanks for studying today!...
Nice solution in c#. Complexity O(n)
ReplyDeletehttp://onestopinterviewprep.blogspot.com/2014/04/find-next-higher-number-with-same-digits.html
Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a Java developer learn from Java Training in Chennai. or learn thru Java Online Training from India . Nowadays Java has tons of job opportunities on various vertical industry.
ReplyDelete