{"id":1019,"date":"2020-06-11T10:25:19","date_gmt":"2020-06-11T10:25:19","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1019"},"modified":"2022-03-29T00:18:16","modified_gmt":"2022-03-29T00:18:16","slug":"largest-number-smaller-than-or-equal-to-n-and-digits-in-non-decreasing-order","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/largest-number-smaller-than-or-equal-to-n-and-digits-in-non-decreasing-order\/","title":{"rendered":"Largest number smaller than or equal to N and digits in non-decreasing order"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Strings<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

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.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
Input:\n1\n50\n\nOutput:\n49\n\nExplanation:\n49 is a non-decreasing number and is also less than or equal to 50.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/h4>\n
\n
1) We traverse from a given number, N<\/code> to 1<\/code>, 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<\/code>.<\/p>\n
2) This approach takes O(N x D)<\/code> time if the number of digits in the number is D<\/code>. This approach takes longer times for larger numbers such as 105<\/sup>, so we find a more efficient approach.<\/p>\n<\/blockquote>\n
Efficient Approach:<\/h4>\n
\n
1) When comparing two digits here, we can have three cases :<\/p>\n
    \n
  • If both are equal<\/strong>, then the maximum number possible is the number itself, as it follows the requirement.<\/li>\n
  • If the number at left is smaller<\/strong> than the right one, then also it follows our requirements, so it remains the same.<\/li>\n
  • But, If the number at left is greater<\/strong> 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. <\/li>\n<\/ul>\n
    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.<\/p>\n
    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<\/code>. Hence the resultant number is our required number. <\/p>\n<\/blockquote>\n
    Example:<\/h4>\n
    \n
    Lets assume given number is 5348<\/code>. So we iterate from second last digit to first digit. We also note lastIndex<\/code> at which pattern does not follow our requirements, we initialise it by -1<\/code>.<\/p>\n
    1) Index = 2<\/code> and value = 4<\/code><\/p>\n
      \n
    • Value right to the current index is 8<\/code>, which is greater than current value. So pattern follows upto current index.<\/li>\n<\/ul>\n
      2) Index = 1<\/code> and value = 3<\/code><\/p>\n
        \n
      • Value right to the current index is 4<\/code>, which is greater than current value. So pattern follows upto current index.<\/li>\n<\/ul>\n
        3) Index = 0<\/code> and value = 5<\/code><\/p>\n
          \n
        • Value right to the current index is 3<\/code>, 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<\/code>. This makes number 4948<\/code>. We also note it’s index i.e. lastIndex = 0<\/code>.<\/li>\n<\/ul>\n
          Now, we have iterated whole number, we note the lastIndex<\/code> if it is -1<\/code> or not. In our case it is not, it’s current value is 0<\/code>, Which means we’ll convert all values to 9 from current index to last index. So, our final answer becomes 4999<\/code>.<\/p>\n<\/blockquote>\n
          Solutions:<\/h3>\n\t\t\t\t\t\t