## Friday, March 18, 2016

### Count 'd' digit positive integers with 0 as a digit - GeeksforGeeks

Count 'd' digit positive integers with 0 as a digit - GeeksforGeeks
Given a number d, representing the number of digits of a positive integer. Find the total count of positive integer (consisting of d digits exactly) which have at-least one zero in them.

```Input : d = 2
Output : 9
The numbers are, 10, 20, 30, 40, 50, 60,
70, 80 and 90.```
One Simple Solution is to traverse through all d digit positive numbers. For every number, traverse through its digits and if there is any 0 digit, increment count (similar to this).
Following are some observations:
1. There are exactly d digits.
2. The number at most significant place can’t be a zero (no leading zeroes allowed).
3. All the other places except the most significant one can contain zero .
```We can place any of {1, 2, ... 9} in D1
Hence D1 can be filled in 9 ways.

Apart from D1 all the other places can be  10 ways.
(we can place 0 as well)
Hence the total numbers having d digits can be given as:
Total =  9*10d-1

Now, let's find the numbers having d digits, that
don't contain zero at any place.
In this case, all the places can be filled in 9 ways.
Hence count of such numbers is given by:
Non_Zero = 9d

Now the count of numbers having at least one zero
can be obtained by subtracting Non_Zero from Total.
Hence Answer would be given by:
9*(10d-1 - 9d-1 ) ```
`int` `findCount(``int` `d)`
`{`
`    ``return` `9*(``pow``(10,d-1) - ``pow``(9,d-1));`
`}`

http://www.geeksforgeeks.org/count-numbers-0-digit/
Count how many integers from 1 to N contains 0’s as a digit.
```Input: n = 155
Output: 24
The numbers having 0 are 10, 20,..90, 100, 101..110,
120, ..150.```
`// Returns 1 if x has 0, else 0`
`int` `has0(``int` `x)`
`{`
`    ``// Traverse througn all digits of`
`    ``// x to check if it has 0.`
`    ``while` `(x)`
`    ``{`
`        ``// If current digit is 0, return true`
`        ``if` `(x % 10 == 0)`
`          ``return` `1;`

`        ``x /= 10;`
`    ``}`

`    ``return` `0;`
`}`

`// Returns count of numbers from 1 to n with 0 as digit`
`int` `getCount(``int` `n)`
`{`
`    ``// Initialize count of numbers having 0 as digit`
`    ``int` `count = 0;`

`    ``// Travers through all numbers and for every number`
`    ``// check if it has 0.`
`    ``for` `(``int` `i=1; i<=n; i++)`
`        ``count += has0(i);`

`    ``return` `count;`
`}`