Queries to count numbers from a given range which are divisible the sum of their digits | C ++ program of the above approach ; Function to check if the number x is divisible by its sum of digits ; Stores sum of digits of x ; Temporarily store x ; Calculate sum of digits of x ; If x is not divisible by sum ; Otherwise ; Function to perform the precomputation ; Iterate from i equals 1 to 1e5 ; Check if i is divisible by sum of its digits ; Convert arr [ ] to prefix sum array ; Driver code ; Given queries ; Using inclusion - exclusion principle , calculate the result
#include <bits/stdc++.h> NEW_LINE using namespace std ; int arr [ 100005 ] ; bool isDivisible ( int x ) { int sum = 0 ; int temp = x ; while ( x != 0 ) { sum += x % 10 ; x /= 10 ; } if ( temp % sum ) return false ; else return true ; } void precompute ( ) { for ( int i = 1 ; i <= 100000 ; i ++ ) { if ( isDivisible ( i ) ) arr [ i ] = 1 ; else arr [ i ] = 0 ; } for ( int i = 1 ; i <= 100000 ; i ++ ) { arr [ i ] = arr [ i ] + arr [ i - 1 ] ; } } int main ( ) { vector < pair < int , int > > Q = { { 5 , 9 } , { 5 , 20 } } ; precompute ( ) ; for ( auto it : Q ) { cout << arr [ it . second ] - arr [ it . first - 1 ] << " STRNEWLINE " ; } return 0 ; }