Queries to count numbers from a given range which are divisible the sum of their digits | java program for 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
import java . io . * ; import java . lang . * ; import java . util . * ; public class GFG { static int arr [ ] = new int [ 100005 ] ; static boolean isDivisible ( int x ) { int sum = 0 ; int temp = x ; while ( x != 0 ) { sum += x % 10 ; x /= 10 ; } if ( temp % sum != 0 ) return false ; else return true ; } static 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 ] ; } } public static void main ( String [ ] args ) { int Q [ ] [ ] = { { 5 , 9 } , { 5 , 20 } } ; precompute ( ) ; for ( int q [ ] : Q ) { System . out . println ( arr [ q [ 1 ] ] - arr [ q [ 0 ] - 1 ] ) ; } } }