# 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 + 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 .

--

--

Feed me code