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

but how?

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 + 5
range 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 above
218765 => 210000 + 8765 [ 5678 - 8765 ] not possible
218765 => 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 8761
we 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 .