#### Concepts Used

Strings

#### Difficulty Level

Medium

#### Problem Statement (Simplified):

For a number given to us, we have to print a number less than or equal to the given number, and having all digits in non-decreasing order.

**See original problem statement here**

#### Test Case

```
Input:
1
50
Output:
49
Explanation:
49 is a non-decreasing number and is also less than or equal to 50.
```

#### Solving Approach :

*Bruteforce Approach:*

1) We traverse from a given number,

`N`

to`1`

, and then check if the given number has all digits in non-decreasing order or not. If yes, we break the loop and print the number. If no such number is found we print`-1`

.2) This approach takes

`O(N x D)`

time if the number of digits in the number is`D`

. This approach takes longer times for larger numbers such as 10^{5}, so we find a more efficient approach.

*Efficient Approach:*

1) When comparing two digits here, we can have three cases :

- If both are
equal, then the maximum number possible is the number itself, as it follows the requirement.- If the number at left is
smallerthan the right one, then also it follows our requirements, so it remains the same.- But, If the number at left is
greaterthan the right one, then it fails for our requirements. Hence, in this case, the maximum number can be achieved if we decrease the left number by 1 and set the right number to 9.2) But if we have the number with digits more than 2, we modify this rule. We compare all the digits from the end to start. If the left side digit is greater than the right one we decrease the left digit by 1. We note it’s index too.

3) After all indexes have been compared to elements to their right, we take the last updated index and set all the values to it’s right to

`9`

. Hence the resultant number is our required number.

#### Example:

Lets assume given number is

`5348`

. So we go through the best sites to learn programming languages and iterate from second last digit to first digit. We also note`lastIndex`

at which pattern does not follow our requirements, we initialise it by`-1`

.1)

`Index = 2`

and`value = 4`

- Value right to the current index is
`8`

, which is greater than current value. So pattern follows upto current index.2)

`Index = 1`

and`value = 3`

- Value right to the current index is
`4`

, which is greater than current value. So pattern follows upto current index.3)

`Index = 0`

and`value = 5`

- Value right to the current index is
`3`

, which is smaller than the current value. So pattern does not follows, so we decrease value of current index by 1 and set value at right to`9`

. This makes number`4948`

. We also note it’s index i.e.`lastIndex = 0`

.Now, we have iterated whole number, we note the

`lastIndex`

if it is`-1`

or not. In our case it is not, it’s current value is`0`

, Which means we’ll convert all values to 9 from current index to last index. So, our final answer becomes`4999`

.

#### Solutions:

#include <stdio.h> #include<string.h> int main() { int test; scanf("%d", &test); while(test--){ char num[100001]; scanf("%s",num); int index, changed = 0; for(int i=strlen(num)-2; i>=0; i--){ if(num[i]>num[i+1]){ num[i] = num[i] - 1; index = i; changed = 1; } } for(int i = index+1; i<strlen(num) && changed == 1; i++) num[i] = '9'; printf("%s\n",num); } }

#include <bits/stdc++.h> using namespace std; int main() { int test; cin>>test; while(test--){ char num[100001]; cin>>num; int index, changed = 0; for(int i=strlen(num)-2; i>=0; i--){ if(num[i]>num[i+1]){ num[i] = num[i] - 1; index = i; changed = 1; } } for(int i = index+1; i<strlen(num) && changed == 1; i++) num[i] = '9'; cout<<num<<endl; } return 0; }

import java.util.*; import java.io.*; import java.lang.Math; public class Main { public static void main(String args[]) throws IOException { Scanner sc= new Scanner(System.in); int test = sc.nextInt(); while(test != 0){ String num = sc.next(); int index = 0, changed = 0; for(int i=num.length()-2; i>=0; i--){ if(num.charAt(i)>num.charAt(i+1)){ num = num.substring(0,i) + (char)((int)(num.charAt(i)) - 1) + num.substring(i+1); index = i; changed = 1; } } for(int i = index+1; i<num.length() && changed == 1; i++) num = num.substring(0,i) + '9' + num.substring(i+1); System.out.println(num); test--; } } }