permutation greater than that number

Count natural numbers whose all permutation are greater than that number

Examples:

Input : n = 15.
Output : 14
Explanation:
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 
13, 14, 15 are the numbers whose all 
permutation is greater than the number
itself. So, output 14.


Input : n = 21.
Output : 18 
1, 2, 3, 4, 5, 6, 7, 8, 9 ,11, 12, 13, 14, 15, 16, 17, 18, 19
are the numbers whose all permutation is greater than or equal
to the number itself.

10 -> Permutation 01 is less than 10 therefore not included.

20 -> Permutation 02 is less than 20 therefore not included.

21 -> Permutation 12 is less than 21 therefore not included.

So, output 18.


Input : n = 100.
Output : 54


Input : n = 7.
Output : 7


method:


 From 1 to 9, all number have this property. So, for n <= 9, output n. 

The number whose all permutation is greater than or equal to that number have all their digits in increasing order.

run a loop from n to 10 and for every number check if its digits are in increasing order or not

if they are in increasing order increment the count

then at the end output count+9

c++ implementation:

#include <iostream>
using namespace std;

int main() {
int n; cin>>n;
int count=0;

if(n<10)
cout<< n;
else
{
    while(n>9)
    {
        count++;
        int t=n;
        int k=12; //any large no(should be atleast two digit)
        while(t)
        {
            int d=t%10;
           
            if(d<=k)
            k=d;
            else
            {
            count--;
            break;
            }
            t=t/10;
        }
        n=n-1;

    }
    cout<< count+9;
}

}


darkmode