Next Greater number
let’s try to find the next greater number with the same set of digit
1234 => 1243, 218765 => 251678
here raw solution comes into our mind somehow we need to rearrange digits
what biggest and smallest number possible after rearranging digits.
very easy to determine when we have a number
a biggest number possible- arrange digits in descending order
biggest number possible for 218765 => 876521
a smallest number possible- arrange digits in ascending order
smallest number possible for 218765 => 125678
so range of possibles numbers after rearranging digits
125678 - 876521 so our answer lies between them
here we observe that digits in the number in descending order then the next greater don’t exist.
cool at least we solved correctly for one case ( not exist)
let divide the given number into a sum of two numbers such way that first one have trailing zeros and second have no trailing zeros.
218765 = 218000 + 765 or X = M + N
here M and N are parts of given X 218 | 765
to find the next greater number, we should add N as least as possible right?
218765 => 218760 + 5range of 5 after rearranging its digit => [ 5, 5]candidate = 218765 oh not accepted as it is not next bigger
let’s break on 6, and further
218765 => 218700 + 65 (56-65)
oh not possible next bigger as 65 is biggest number possible after rearranging its digit.218765 => 218000 + 765 not possible same case above218765 => 210000 + 8765 [ 5678 - 8765 ] not possible218765 => 200000 + 18765 [ 15678 - 87651 ]as you see sorter segment 18765 must rearrange to get answer
so far we are able to get a shorter segment that must be rearranged to get the result.
but still, we have the same point no no
18765 how we can get the next number for this I have to place a slightly bigger digit on the left-most digit position. here notice all digit here bigger than the leftmost digit. and we have to find next greater number for 18765
18765 => 58761 as 5 is slightly greater than 1 from available option
hey, 58761 is bigger but can I add it 200000 + 58761 = 258761
ye it giving me a bigger number than the given number
no, don’t be over-excited again
58761 => 5 + 8761 rearranging 8761 we get smaller 1678 and bigger 8761we want to 8761 as small as possible why ? 250000 + (8761) 250000 is already bigger than 218765 (given number)if we add 200000 + 51678 => 251678 this is our answer
here few observations
in beginning first few segments are rejected because they have digits in descending order and we can’t make any greater number from them
once we found a segment that is not descending we stopped why? simple we have a replacement of leftmost digit to make it a bigger number
after replacing we again thought can it answer no because we have still a shorter segment after replacing the leftmost digit to the next bigger digit.
and we are done.
Time complexity : O(d) d is number of digits
Dont forget to clap if you enjoy it .