Count positive integers with 0 as a digit and maximum 'd' digits - GeeksforGeeks

Count positive integers with 0 as a digit and maximum 'd' digits - GeeksforGeeks
Given a number d, representing the number of digits of a number. Find the total count of positive integers which have at-least one zero in them and consist d or less digits.

Input : d = 1
Output : 0
There's no natural number of 1 digit that contains a zero.

Input : d = 2
Output : 9

Input : d = 3
Output : 180
For d = 3, we've to count numbers from 1 to 999, that have 
atleast one zero in them.
Similarly for d=4, we'd check every number from 1 to 9999. 

i'th term of G.P. 1 = 9*10i - 1  where 1 <= i <= d
i'th term of G.P. 2 = 9*9i - 1 where 1 <= i <= d
The final answer is nothing but,

   
Sum of G.P 1 = 9*(10d - 1)/(10-1) 
             = 9*(10d - 1)/9
Similarly,
Sum of G.P 2 = 9*(9d - 1)/(9-1) 
             = 9*(9d - 1)/8
Using the above facts, we can optimize the solution to run in O(1) 

int findCountUpto(int d)

{

    // Sum of two GP series

    int GP1_Sum = 9*((pow(10,d)-1)/9);

    int GP2_Sum = 9*((pow(9,d)-1)/8);

 

    return GP1_Sum - GP2_Sum;

}

Time Complexity : O(d)
Auxiliary Space : O(1)

If we observe carefully the problem is very similar to the one which we had discussed in our first set. For a given d, we can get the required answer if we find numbers that have 0s and consist of digits 1, 2, 3….., d. Finally we can add them to get the output.

int findCount(int d)

{

    return 9*(pow(10,d-1) - pow(9,d-1));

}

 

// utility function to count the required answer

int findCountUpto(int d)

{

    // Count of numbers with digits smaller than

    // or equal to d.

    int totalCount = 0;

    for (int i=1; i<=d; i++)

        totalCount += findCount(i);

 

    return totalCount;

}

Read full article from Count positive integers with 0 as a digit and maximum 'd' digits - GeeksforGeeks