Last Updated on March 23, 2022 by Ria Pathak
CONCEPTS USED:
Searching
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
Given a number
N, find the smallest number that has same set-of-digits asNand is greater thanN. IfNis the greatest possible number with its set-of-digits, then print the same numberN.
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,
12345will change to12354.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,2is the first digit that is less than5so2is our ithindex digit.Now again traverse to the right of this index
iand find the smallest digit that is just greater than the digit at ith index. Let’s say the found index isjat the right ofi. Now if we traverse right of2, the smallest digit that is greater than2is3(not5).Swap digits at ith and jth index. After swapping
125321becomes135221.Sort digits from
(i+1)to the rightmost index in increasing order. After sorting,135221becomes131225, which is our required solution.
OPTIMIZATIONS:
A few optimizations can be made in this approach and significantly improve the
Time Complexityof the approach.The
Linear Searchused inStep-2can be replaced withBinary Searchas the right digits are already sorted. This reducesTime ComplexityfromO(n)toO(logn).The
Sortingused inStep-4can be done inO(n)instead ofO(nlogn)as only one digit needs to be repositioned else all are already sorted.This
Optimizationwould improve our solution fromO(n+n+nlogn)toO(n+logn+n)giving overall time complexity ofO(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) print(*arr)# your code goes here
[forminator_quiz id="482"]
This article tried to discuss Searching. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.