Count numbers from 1 to n that have 4 as a digit | Python3 program to count numbers having 4 as a digit ; Function to count numbers from 1 to n that have 4 as a digit ; Base case ; d = number of digits minus one in n . For 328 , d is 2 ; computing count of numbers from 1 to 10 ^ d - 1 , d = 0 a [ 0 ] = 0 d = 1 a [ 1 ] = count of numbers from 0 to 9 = 1 d = 2 a [ 2 ] = count of numbers from 0 to 99 = a [ 1 ] * 9 + 10 = 19 d = 3 a [ 3 ] = count of numbers from 0 to 999 = a [ 2 ] * 19 + 100 = 171 ; Computing 10 ^ d ; Most significant digit ( msd ) of n , For 328 , msd is 3 which can be obtained using 328 / 100 ; If MSD is 4. For example if n = 428 , then count of numbers is sum of following . 1 ) Count of numbers from 1 to 399 2 ) Count of numbers from 400 to 428 which is 29. ; IF MSD > 4. For example if n is 728 , then count of numbers is sum of following . 1 ) Count of numbers from 1 to 399 and count of numbers from 500 to 699 , i . e . , " a [ 2 ] ▁ * ▁ 6" 2 ) Count of numbers from 400 to 499 , i . e . 100 3 ) Count of numbers from 700 to 728 , recur for 28 ; IF MSD < 4. For example if n is 328 , then count of numbers is sum of following . 1 ) Count of numbers from 1 to 299 a 2 ) Count of numbers from 300 to 328 , recur for 28 ; Driver Code
import math as mt NEW_LINE def countNumbersWith4 ( n ) : NEW_LINE INDENT if ( n < 4 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT d = int ( mt . log10 ( n ) ) NEW_LINE a = [ 1 for i in range ( d + 1 ) ] NEW_LINE a [ 0 ] = 0 NEW_LINE if len ( a ) > 1 : NEW_LINE INDENT a [ 1 ] = 1 NEW_LINE DEDENT for i in range ( 2 , d + 1 ) : NEW_LINE INDENT a [ i ] = a [ i - 1 ] * 9 + mt . ceil ( pow ( 10 , i - 1 ) ) NEW_LINE DEDENT p = mt . ceil ( pow ( 10 , d ) ) NEW_LINE msd = n // p NEW_LINE if ( msd == 4 ) : NEW_LINE INDENT return ( msd ) * a [ d ] + ( n % p ) + 1 NEW_LINE DEDENT if ( msd > 4 ) : NEW_LINE INDENT return ( ( msd - 1 ) * a [ d ] + p + countNumbersWith4 ( n % p ) ) NEW_LINE DEDENT return ( msd ) * a [ d ] + countNumbersWith4 ( n % p ) NEW_LINE DEDENT n = 328 NEW_LINE print ( " Count ▁ of ▁ numbers ▁ from ▁ 1 ▁ to " , n , " that ▁ have ▁ 4 ▁ as ▁ a ▁ digit ▁ is " , countNumbersWith4 ( n ) ) NEW_LINE