Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Greater And Least

Last Updated on March 23, 2022 by Ria Pathak

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.

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:

```
#include < stdio.h >

//function for swapping two values
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

//sorting a subarray in increasing order
void sortSubarray(int number[], int i, int j)
{
while (i < j)
{
swap(number, i, j);
i += 1;
j -= 1;
}
}

void findNextGreaterNumber(int arr[], int n)
{
int lastDigitSeen = arr[n - 1], i, j;
for (i = n - 2; i >= 0; i--)
{
if (lastDigitSeen > arr[i])
break;
lastDigitSeen = arr[i];
}
if (i >= 0)
{
for (j = n - 1; j > i; j--)
{
if (arr[j] > arr[i])
break;
}

swap(arr, i, j);
sortSubarray(arr, i + 1, n - 1);
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
long long n;
scanf("%lld", &n);
int count = 0;
long long num = n;

//count the number of digits in n
while (num > 0)
{
num /= 10;
count++;
}

//storing all digits of n into an array
int arr[count];
int i = count - 1;
while (n > 0)
{
arr[i--] = n % 10;
n /= 10;
}

findNextGreaterNumber(arr, count);

//printing all digits of the resultant number
for (int j = 0; j < count; j++)
printf("%d", arr[j]);
printf("\n");
}
return 0;
}
```
```#include <  bits/stdc++.h >
using namespace std;

//function for swapping two values
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

//sorting a subarray in increasing order
void sortSubarray(int number[], int i, int j)
{
while (i < j)
{
swap(number, i, j);
i += 1;
j -= 1;
}
}

void findNextGreaterNumber(int arr[], int n)
{
int lastDigitSeen = arr[n - 1], i, j;
for (i = n - 2; i >= 0; i--)
{
if (lastDigitSeen > arr[i])
break;
lastDigitSeen = arr[i];
}
if (i >= 0)
{
for (j = n - 1; j > i; j--)
{
if (arr[j] > arr[i])
break;
}

swap(arr, i, j);
sortSubarray(arr, i + 1, n - 1);
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
long long n;
cin >> n;
int count = 0;
long long num = n;

//count the number of digits in n
while (num > 0)
{
num /= 10;
count++;
}

//storing all digits of n into an array
int arr[count];
int i = count - 1;
while (n > 0)
{
arr[i--] = n % 10;
n /= 10;
}

findNextGreaterNumber(arr, count);

//printing all digits of the resultant number
for (int j = 0; j < count; j++)
cout << arr[j];
cout << "\n";
}
return 0;
}
```
```#include <  bits/stdc++.h >
using namespace std;

string NextGreater(string str){
int n = str.size();
for(int i=n-2; i>=0; i--){
if(str[i] < str[i+1]){
sort(str.begin() + i + 1, str.end());
auto it = upper_bound(str.begin() + i + 1, str.end(), str[i]);
int index = it - str.begin();
swap(str[index], str[i]);
break;
}
}
return str;
}
int main()
{
int t; cin>>t;
while(t--){
string str; cin>>str;
cout<<"\n"<

```
```import java.util.*;
import java.io.*;

public class Main {
static void swap(long []arr, int i, int j)
{
long temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

//sorting a subarray in increasing order
static void sortSubarray(long []number, int i, int j)
{
while (i < j)
{
swap(number, i, j);
i += 1;
j -= 1;
}
}

static void findNextGreaterNumber(long []arr, int n)
{
long lastDigitSeen = arr[n - 1];
int i, j;
for (i = n - 2; i >= 0; i--)
{
if (lastDigitSeen > arr[i])
break;
lastDigitSeen = arr[i];
}
if (i >= 0)
{
for (j = n - 1; j > i; j--)
{
if (arr[j] > arr[i])
break;
}

swap(arr, i, j);
sortSubarray(arr, i + 1, n - 1);
}
}
public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t != 0)
{
long n = sc.nextLong();
int count = 0;
long num = n;

//count the number of digits in n
while (num > 0)
{
num /= 10;
count++;
}

//storing all digits of n into an array
long arr[] = new long[count];
int i = count - 1;
while (n > 0)
{
arr[i--] = n % 10;
n /= 10;
}

findNextGreaterNumber(arr, count);

//printing all digits of the resultant number
for (int j = 0; j < count; j++)
System.out.print(arr[j]);
System.out.println();
t--;
}

}
}
```
```n = int(input())
num = n
count = 0

while num:
num //= 10
count += 1

arr = [0 for i in range(count)]
i = count - 1

while n:
arr[i] = n % 10
n //= 10
i -=1

def swap(arr, i , j):
arr[i], arr[j] = arr[j], arr[i]

def sortSubarray(number, i ,j):
while i < j:
swap(number, i , j)
i += 1
j -= 1

def findNextGreater(arr, n):
lastDigitSeen = arr[-1]

for i in range(n - 2, -1, -1):
if lastDigitSeen > arr[i]:
break
lastDigitSeen = arr[i]

if i>=0:

for j in range(n - 1, i, -1):
if arr[j] > arr[i]:
break
swap(arr, i, j)
sortSubarray(arr, i + 1, n - 1)
return arr

arr = findNextGreater(arr, count)