# Greater And Least

Searching

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:

1. 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`.

2. If the digits are all sorted in strictly increasing order, then just swap the last two digits. For example, `12345` will change to `12354`.

3. 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:

1. 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 ithindex digit.

2. Now again traverse to the right of this index `i` and find the smallest digit that is just greater than the digit at ith 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`).

3. Swap digits at ith and jth index. After swapping `125321` becomes `135221`.

4. Sort digits from `(i+1)` to the rightmost index in increasing order. After sorting, `135221` becomes `131225`, which is our required solution.

#### OPTIMIZATIONS:

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

2. 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)`.

3. 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.

4. 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″]