Largest number smaller than or equal to N and digits in non-decreasing order

Last Updated on March 29, 2022 by Ria Pathak

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⁵, 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 smaller than the right one, then also it follows our requirements, so it remains the same.
• But, If the number at left is greater than 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 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--;
      }

  }
}

for _ in range(int(input())):
	
	num = list(input())
	changed = 0

	for i in range(len(num) - 2, -1, -1):
		if num[i] > num[i + 1]:
			num[i] = str(int(num[i]) - 1)
			index = i
			changed = 1

	if changed == 1:
		
		for i in range(index + 1, len(num)):
			num[i] = "9"

	print(*num, sep = "")

[forminator_quiz id="1024"]

This article tried to discuss Strings. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming.