Queries to count numbers from a range which does not contain digit K in their decimal or octal representation | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool contains ( int num , int K , int base ) { bool isThere = 0 ; while ( num ) { int remainder = num % base ; if ( remainder == K ) { isThere = 1 ; } num /= base ; } return isThere ; } void count ( int n , int k , vector < vector < int > > v ) { int pref [ 1000005 ] = { 0 } ; for ( int i = 1 ; i < 1e6 + 5 ; i ++ ) { bool present = contains ( i , k , 10 ) || contains ( i , k , 8 ) ; pref [ i ] += pref [ i - 1 ] + present ; } for ( int i = 0 ; i < n ; ++ i ) { cout << v [ i ] [ 1 ] - v [ i ] [ 0 ] + 1 - ( pref [ v [ i ] [ 1 ] ] - pref [ v [ i ] [ 0 ] - 1 ] ) << ' ▁ ' ; } } int main ( ) { int K = 7 ; vector < vector < int > > Q = { { 2 , 5 } , { 1 , 15 } } ; int N = Q . size ( ) ; count ( N , K , Q ) ; }