# Count numbers that don’t contain 3

Given a number n, write a function that returns count of numbers from 1 to n that don’t contain digit 3 in their decimal representation.

Examples:

```Input: n = 10
Output: 9

Input: n = 45
Output: 31
// Numbers 3, 13, 23, 30, 31, 32, 33, 34,
// 35, 36, 37, 38, 39, 43 contain digit 3.

Input: n = 578
Ouput: 385
```

## We strongly recommend that you click here and practice it, before moving on to the solution.

Solution:
We can solve it recursively. Let count(n) be the function that counts such numbers.

```'msd' --> the most significant digit in n
'd'   --> number of digits in n.

count(n) = n if n < 3

count(n) = n - 1 if 3 <= n  10 and msd is not 3

count(n) = count( msd * (10^(d-1)) - 1)
if n > 10 and msd is 3
```
```Let us understand the solution with n = 578.
count(578) = 4*count(99) + 4 + count(78)
The middle term 4 is added to include numbers
100, 200, 400 and 500.

Let us take n = 35 as another example.
count(35) = count (3*10 - 1) = count(29)
```

## C/C++

 `#include ` ` `  `/* returns count of numbers which are in range from 1 to n and don't contain 3  ` `   ``as a digit */` `int` `count(``int` `n) ` `{ ` `    ``// Base cases (Assuming n is not negative) ` `    ``if` `(n < 3) ` `        ``return` `n; ` `    ``if` `(n >= 3 && n < 10) ` `       ``return` `n-1; ` ` `  `    ``// Calculate 10^(d-1) (10 raise to the power d-1) where d is ` `    ``// number of digits in n. po will be 100 for n = 578 ` `    ``int` `po = 1; ` `    ``while` `(n/po > 9) ` `        ``po = po*10; ` ` `  `    ``// find the most significant digit (msd is 5 for 578) ` `    ``int` `msd = n/po; ` ` `  `    ``if` `(msd != 3) ` `      ``// For 578, total will be 4*count(10^2 - 1) + 4 + count(78) ` `      ``return` `count(msd)*count(po - 1) + count(msd) + count(n%po); ` `    ``else` `      ``// For 35, total will be equal to count(29) ` `      ``return` `count(msd*po - 1); ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``printf` `(``"%d "``, count(578)); ` `    ``return` `0; ` `} `

## Java

 `// Java program to count numbers that not contain 3 ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `    ``// Function that returns count of numbers which  ` `    ``// are in range from 1 to n  ` `    ``// and not contain 3 as a digit ` `    ``static` `int` `count(``int` `n) ` `    ``{ ` `        ``// Base cases (Assuming n is not negative) ` `        ``if` `(n < ``3``) ` `            ``return` `n; ` `        ``if` `(n >= ``3` `&& n < ``10``) ` `            ``return` `n-``1``; ` `  `  `        ``// Calculate 10^(d-1) (10 raise to the power d-1) where d is ` `        ``// number of digits in n. po will be 100 for n = 578 ` `        ``int` `po = ``1``; ` `        ``while` `(n/po > ``9``) ` `            ``po = po*``10``; ` `  `  `        ``// find the most significant digit (msd is 5 for 578) ` `        ``int` `msd = n/po; ` `  `  `        ``if` `(msd != ``3``) ` `            ``// For 578, total will be 4*count(10^2 - 1) + 4 + count(78) ` `            ``return` `count(msd)*count(po - ``1``) + count(msd) + count(n%po); ` `        ``else` `            ``// For 35, total will be equal to count(29) ` `            ``return` `count(msd*po - ``1``); ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `n = ``578``; ` `        ``System.out.println(count(n)); ` `    ``} ` `} ` ` `  `// Contributed by Pramod Kumar `

## Python

 `# Python program to count numbers upto n that don't contain 3 ` ` `  `# Returns count of numbers which are in range from 1 to n ` `# and don't contain 3 as a digit ` `def` `count(n): ` `     `  `    ``# Base Cases ( n is not negative) ` `    ``if` `n < ``3``: ` `        ``return` `n ` `    ``elif` `n >``=` `3` `and` `n < ``10``: ` `        ``return` `n``-``1` `         `  `    ``# Calculate 10^(d-1) ( 10 raise to the power d-1 ) where d ` `    ``# is number of digits in n. po will be 100 for n = 578 ` `     `  `    ``po ``=` `1` `    ``while` `n``/``po > ``9``: ` `        ``po ``=` `po ``*` `10` `     `  `    ``# Find the MSD ( msd is 5 for 578 ) ` `    ``msd ``=` `n``/``po ` `     `  `    ``if` `msd !``=` `3``: ` `        ``# For 578, total will be 4*count(10^2 - 1) + 4 + ccount(78) ` `        ``return` `count(msd) ``*` `count(po``-``1``) ``+` `count(msd) ``+` `count(n``%``po) ` `    ``else``: ` `        ``# For 35 total will be equal to count(29) ` `        ``return` `count(msd ``*` `po ``-` `1``) ` `         `  `# Driver Program ` `n ``=` `578` `print` `count(n) ` ` `  `# Contributed by Harshit Agrawal `

/div>

## C#

 `// C# program to count numbers that not ` `// contain 3 ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Function that returns count of  ` `    ``// numbers which are in range from  ` `    ``// 1 to n and not contain 3 as a ` `    ``// digit ` `    ``static` `int` `count(``int` `n) ` `    ``{ ` `         `  `        ``// Base cases (Assuming n is  ` `        ``// not negative) ` `        ``if` `(n < 3) ` `            ``return` `n; ` `        ``if` `(n >= 3 && n < 10) ` `            ``return` `n-1; ` ` `  `        ``// Calculate 10^(d-1) (10 raise  ` `        ``// to the power d-1) where d is ` `        ``// number of digits in n. po will ` `        ``// be 100 for n = 578 ` `        ``int` `po = 1; ` `         `  `        ``while` `(n / po > 9) ` `            ``po = po * 10; ` ` `  `        ``// find the most significant  ` `        ``// digit (msd is 5 for 578) ` `        ``int` `msd = n / po; ` ` `  `        ``if` `(msd != 3) ` `         `  `            ``// For 578, total will be ` `            ``// 4*count(10^2 - 1) + 4 + ` `            ``// count(78) ` `            ``return` `count(msd) * count(po - 1)  ` `                ``+ count(msd) + count(n % po); ` `        ``else` `         `  `            ``// For 35, total will be equal  ` `            ``// to count(29) ` `            ``return` `count(msd * po - 1); ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``int` `n = 578; ` `         `  `        ``Console.Write(count(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007. `

## PHP

 `= 3 && ``\$n` `< 10) ` `        ``return` `\$n``-1; ` ` `  `    ``// Calculate 10^(d-1) (10 raise to the  ` `    ``// power d-1) where d is number of digits  ` `    ``// in n. po will be 100 for n = 578 ` `    ``\$po` `= 1; ` `    ``for``(``\$x` `= ``intval``(``\$n``/``\$po``); ``\$x` `> 9; ``\$x` `= ``intval``(``\$n``/``\$po``)) ` `        ``\$po` `= ``\$po``*10; ` ` `  `    ``// find the most significant digit (msd is 5 for 578) ` `    ``\$msd` `= ``intval``(``\$n` `/ ``\$po``); ` ` `  `    ``if` `(``\$msd` `!= 3) ` `     `  `    ``// For 578, total will be 4*count(10^2 - 1) ` `    ``// + 4 + count(78) ` `    ``return` `count1(``\$msd``) * count1(``\$po` `- 1) + ` `                ``count1(``\$msd``) + count1(``\$n``%``\$po``); ` `    ``else` `     `  `    ``// For 35, total will be equal to count(29) ` `    ``return` `count1(``\$msd``*``\$po` `- 1); ` `} ` ` `  `// Driver program to test above function ` `    ``echo` `count1(578); ` ` `  `// This code is contributed by mits. ` `?> `

Output:

`385`

## tags:

Mathematical School Programming Mathematical