## Friday, March 18, 2016

### 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