Count numbers 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 ; Base Cases ( n is not negative ) ; 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 ; Find the MSD ( msd is 5 for 578 ) ; For 578 , total will be 4 * count ( 10 ^ 2 - 1 ) + 4 + ccount ( 78 ) ; For 35 total will be equal to count ( 29 ) ; Driver Program
def count ( n ) : NEW_LINE INDENT if n < 3 : NEW_LINE INDENT return n NEW_LINE DEDENT elif n >= 3 and n < 10 : NEW_LINE INDENT return n - 1 NEW_LINE DEDENT po = 1 NEW_LINE while n / po > 9 : NEW_LINE INDENT po = po * 10 NEW_LINE DEDENT msd = n / po NEW_LINE if msd != 3 : NEW_LINE INDENT return count ( msd ) * count ( po - 1 ) + count ( msd ) + count ( n % po ) NEW_LINE DEDENT else : NEW_LINE INDENT return count ( msd * po - 1 ) NEW_LINE DEDENT DEDENT n = 578 NEW_LINE print count ( n ) NEW_LINE