{"id":10048,"date":"2022-09-27T10:49:04","date_gmt":"2022-09-27T10:49:04","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=10048"},"modified":"2022-10-10T09:33:28","modified_gmt":"2022-10-10T09:33:28","slug":"count-natural-numbers-whose-all-permutation-are-greater-than-that-number","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/count-natural-numbers-whose-all-permutation-are-greater-than-that-number\/","title":{"rendered":"Count natural numbers whose all permutation are greater than that number"},"content":{"rendered":"

\"\"<\/p>\n

Problem statement<\/h3>\n

Given a number n, you have to find the count of all such numbers that satisfies the following condition:
\nFor any number x, all the permutations of x must be greater than or equal to x.<\/p>\n

Input<\/strong>: Integer.
\nOutput<\/strong>: Integer.<\/p>\n

Test cases:<\/h3>\n

Input<\/strong>: 14
\nOutput<\/strong>: 13<\/p>\n

Explanation:<\/h3>\n

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14 are all such numbers whose all the permutations are greater than or equal to them. <\/p>\n

Naive Approach<\/h3>\n

A simple approach is to traverse each number from 1 to n and check if the digits in that number are in non – decreasing order or not. If yes, then increment the count by 1.<\/p>\n

Code implementation<\/h3>\n\n

Output<\/strong>:
\n14<\/p>\n

Time complexity:<\/strong> O(n d). Where n is the given number and d is the number of digits in n. We have to traverse from 1 to n and for each number we have to traverse its digits. Hence, the time complexity will be O(n <\/em> d).<\/p>\n

Space Complexity:<\/strong> O(n d). Where n is the given number and d is the number of digits in n. We have to traverse from 1 to n and for each number we are storing its digits in an array<\/a>. Hence, the space complexity O(n <\/em> d).<\/p>\n

Approach – Using Stack<\/h3>\n

In the example, we can observe that:
\nAll numbers from 1 to 9 are valid.
\nAll valid numbers have their digits in non – decreasing order.<\/p>\n

By using these observations, we can come up with a stack based solution. In the stack approach, we will push all the numbers from 1 to 9 in the stack. Now, we will pop the top element and try to make all valid numbers from the top element. To make such numbers, the second digit can be from (top element)%10 to 9. If this number is less than n, then this is a valid number. We will increment the count by 1 and push this number in the stack.<\/p>\n

Algorithm<\/h3>\n
    \n
  1. Initialize a new stack.<\/li>\n
  2. Iterate \u2018i\u2019 from 1 to 9:
    \ni. If \u2018i\u2019 is less than \u2018n\u2019, push \u2018i\u2019 to stack and increment the result by 1.
    \nii. While stack is not empty
    \na. Pop the top element.
    \nb. Iterate \u2018j\u2019 from top % 10 to 9
    \ni. If (topElement * 10 + j) is less than \u2018n\u2019, push it to the stack and increment the result by 1.<\/li>\n
  3. Return result.<\/li>\n<\/ol>\n

    Dry Run:<\/h3>\n

    \"\"<\/p>\n

    Start pushing from 1 to 9 to the stack<\/p>\n

    \"\"<\/p>\n

    Pop the top of the stack and create valid numbers from it.
    \n\"\"
    \nTop element = 1
    \nNow, the second digit will be from top element % 10 to 9
    \nThe generated numbers are: 11,12,13,14,15,16,17,18,19<\/p>\n

    Out of this 11,12,13,14 are less than equal to n<\/p>\n

    We will add this number to the stack, increment our count for each valid number and continue.<\/p>\n

    \"\"<\/p>\n

    Here, we can see that if we add another digit to any of the number in the stack, it will be greater than n and hence not valid.<\/p>\n

    \"\"<\/p>\n

    So, we will continue by pushing the numbers from 2 to 9, but any number starting from 2 to 9 will be greater than 14.
    \nSo we can see that valid numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14<\/p>\n

    Code Implementation:<\/h3>\n\t\t\t\t\t\t