#### CONCEPTS USED:

Searching

#### DIFFICULTY LEVEL:

Hard

#### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Given a number

`N`

, find the smallest number that has same set-of-digits as`N`

and is greater than`N`

. If`N`

is the greatest possible number with its set-of-digits, then print the same number`N`

.

**See original problem statement here**

#### For Example:

```
Input : "12345"
Output : "12354"
```

```
Input : "54321"
Output : "54321"
Explanation : No number is greater than 54321 with same set of digits, thats why print same number.
```

```
Input : "12321"
Output : "13122"
```

**OBSERVATIONS**:

If the digits are all sorted in strictly descending order, then the number itself would be our answer as there is no bigger number than that.

For example,`54321`

.If the digits are all sorted in strictly increasing order, then just swap the last two digits. For example,

`12345`

will change to`12354`

.For all other cases, we need to process all the digits in the number from right to left as we need to find the smallest of the greater numbers.

#### SOLVING APPROACH:

Start traversing the given number from rightmost digit till you reach a digit that is just smaller than its right digit, say index of this digit be

`i`

.

:For example

`N`

`=`

`125321`

, here if we scan from right to left,`2`

is the first digit that is less than`5`

so`2`

is our i^{th}index digit.Now again traverse to the right of this index

`i`

and find the smallest digit that is just greater than the digit at i^{th}index. Let’s say the found index is`j`

at the right of`i`

. Now if we traverse right of`2`

, the smallest digit that is greater than`2`

is`3`

(not`5`

).Swap digits at i

^{th}and j^{th}index. After swapping`125321`

becomes`135221`

.Sort digits from

`(i+1)`

to the rightmost index in increasing order. After sorting,`135221`

becomes`131225`

, which is our required solution.

#### OPTIMIZATIONS:

A few optimizations can be made in this approach and significantly improve the Time Complexity of the approach according to the data structures and algorithms in c++.

The

`Linear Search`

used in`Step-2`

can be replaced with`Binary Search`

as the right digits are already sorted. This reduces`Time Complexity`

from`O(n)`

to`O(logn)`

.The

`Sorting`

used in`Step-4`

can be done in`O(n)`

instead of`O(nlogn)`

as only one digit needs to be repositioned else all are already sorted.This

`Optimization`

would improve our solution from`O(n+n+nlogn)`

to`O(n+logn+n)`

giving overall time complexity of`O(n)`

, where

`n = number-of-digits-of-a-given-number`

.

#### SOLUTIONS:

[TABS_R id=468]

[forminator_quiz id=”482″]