Queries to count numbers from a range which does not contain digit K in their decimal or octal representation | Function to check if the given digit ' K ' is present in the decimal and octal representations of num or not ; Stores if the digit exists or not ; Iterate till nums is non - zero ; Find the remainder ; If the remainder is K ; Function to count the numbers in the range [ 1 , N ] such that it doesn ' t ▁ contain ▁ the ▁ digit ▁ ' K ' in its decimal and octal representation ; Stores count of numbers in the range [ 0 , i ] that contains the digit ' K ' in its octal or decimal representation ; Traverse the range [ 0 , 1e6 + 5 ] ; Check if i contains the digit ' K ' in its decimal or octal representation ; Update pref [ i ] ; Print the answer of queries ; Driver Code ; Function Call
def contains ( num , K , base ) : NEW_LINE INDENT isThere = 0 NEW_LINE while ( num ) : NEW_LINE INDENT remainder = num % base NEW_LINE if ( remainder == K ) : NEW_LINE INDENT isThere = 1 NEW_LINE DEDENT num //= base NEW_LINE DEDENT return isThere NEW_LINE DEDENT def count ( n , k , v ) : NEW_LINE INDENT pref = [ 0 ] * 1000005 NEW_LINE for i in range ( 1 , 10 ** 6 + 5 ) : NEW_LINE INDENT present = contains ( i , k , 10 ) or contains ( i , k , 8 ) NEW_LINE pref [ i ] += pref [ i - 1 ] + present NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT print ( v [ i ] [ 1 ] - v [ i ] [ 0 ] + 1 - ( pref [ v [ i ] [ 1 ] ] - pref [ v [ i ] [ 0 ] - 1 ] ) , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT K = 7 NEW_LINE Q = [ [ 2 , 5 ] , [ 1 , 15 ] ] NEW_LINE N = len ( Q ) NEW_LINE count ( N , K , Q ) NEW_LINE DEDENT