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 ( Assuming 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 most significant digit ( msd is 5 for 578 ) ; For 578 , total will be 4 * count ( 10 ^ 2 - 1 ) + 4 + count ( 78 ) ; For 35 , total will be equal to count ( 29 ) ; Driver program to test above function
< ? php function count1 ( $ n ) { if ( $ n < 3 ) return $ n ; if ( $ n >= 3 && $ n < 10 ) return $ n - 1 ; $ po = 1 ; for ( $ x = intval ( $ n / $ po ) ; $ x > 9 ; $ x = intval ( $ n / $ po ) ) $ po = $ po * 10 ; $ msd = intval ( $ n / $ po ) ; if ( $ msd != 3 ) return count1 ( $ msd ) * count1 ( $ po - 1 ) + count1 ( $ msd ) + count1 ( $ n % $ po ) ; else return count1 ( $ msd * $ po - 1 ) ; } echo count1 ( 578 ) ; ? >