Count natural numbers whose all permutation are greater than that number

Last Updated on October 10, 2022 by Gokul Kannan

Problem statement

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

Input: Integer.
Output: Integer.

Test cases:

Input: 14
Output: 13

Explanation:

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.

Naive Approach

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.

Code implementation

Output:
14

Time complexity: 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 d).

Space Complexity: 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. Hence, the space complexity O(n d).

Approach – Using Stack

In the example, we can observe that:
All numbers from 1 to 9 are valid.
All valid numbers have their digits in non – decreasing order.

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.

Algorithm

1. Initialize a new stack.
2. Iterate ‘i’ from 1 to 9:
   i. If ‘i’ is less than ‘n’, push ‘i’ to stack and increment the result by 1.
   ii. While stack is not empty
   a. Pop the top element.
   b. Iterate ‘j’ from top % 10 to 9
   i. If (topElement * 10 + j) is less than ‘n’, push it to the stack and increment the result by 1.
3. Return result.

Dry Run:

Start pushing from 1 to 9 to the stack

Pop the top of the stack and create valid numbers from it.

Top element = 1
Now, the second digit will be from top element % 10 to 9
The generated numbers are: 11,12,13,14,15,16,17,18,19

Out of this 11,12,13,14 are less than equal to n

We will add this number to the stack, increment our count for each valid number and continue.

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.

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.
So we can see that valid numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

Code Implementation:

public class Main
{
	public static void main(String[] args) {
		int n = 14;
		System.out.println(findCount(n));
	}
	
	public static int findCount(int n){
	    int result = 0;
 
        Stack<Integer> st = new Stack<>();
        
        // Start pushing the number from 1 to 9.
        for (int i = 1; i <= 9; i++)
        {
 
            if (i <= n) {
                st.push(i);
                result++;
            }
 
            // Take a number from the stack.
            while (!st.empty())
            {
                int topElement = s.pop();
                
                // The following digits can be from (top element)%10 to 9
                for (int j = topElement % 10; j <= 9; j++)
                {
                    int x = topElement * 10 + j;
                    if (x <= n) {
                        s.push(x);
                        result++;
                    }
                }
            }
        }
 
        return result;
	}
}

Output:
14

Time complexity: O(x), where x is the count of all the valid answers.

Space Complexity: O(x). We are using a stack which can have at most x numbers.

We tried to discuss the Delete consecutive same words in a sequence. We hope this article gives you a better understanding of Delete consecutive same words in a sequence. PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.