# Queries to count numbers from a given range which are divisible the sum of their digits

Given an array** Q[][]** consisting of **N** queries of the form **{L, R}**, the task for each query is to find the total count of the numbers from the range** [L, R]** which are divisible by the sum of their digits.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:Q[][]= {{5, 9}, {5, 20}}Output:

5

9Explanation:

Query 1: The numbers in the range [5, 9] which are divisible by the sum of their digits are {5, 6, 7, 8, 9}.

Query 2: The numbers in the range [5, 20] which are divisible by the sum of their digits are {5, 6, 7, 8, 9, 10, 12, 18, 20}.

Input:Q[][] = {{1, 30}, {13, 15}}Output:

17

0Explanation:

Query 1: The numbers in the range [5, 9] which are divisible by the sum of their digits are {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 18, 20, 21, 24, 27, 30}.

Query 2: No such number exists in the range [13, 15].

**Approach: **The problem can be solved using the inclusion-exclusion principle and prefix sum array technique.

Follow the steps below to solve the given problem:

- Initialize an array
**arr[]**to store at every i^{th}index, the count of numbers up to i which are divisible by the sum of their digits. - Iterate over the range
**[1, 10**using a variable, say^{5}]**i**, and for every**i**^{th}element, check if**i**is divisible by the sum of its digits.- If found to be true, set
**arr[i] = 1**. - Otherwise, set
**arr[i] = 0**.

- If found to be true, set
- Modify the array arr[] to its prefix sum array.
- Traverse the array
**Q[][]**and for each query, calculate the total count of required numbers from the range**[L, R]**, which is equal to**arr[R] – arr[L – 1]**.

Below is the implementation of the above approach:

## C++

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

## Java

`// java program for the above approach` `import` `java.io.*;` `import` `java.lang.*;` `import` `java.util.*;` `public` `class` `GFG {` ` ` `static` `int` `arr[] = ` `new` `int` `[` `100005` `];` ` ` `// Function to check if the number x` ` ` `// is divisible by its sum of digits` ` ` `static` `boolean` `isDivisible(` `int` `x)` ` ` `{` ` ` `// Stores sum of digits of x` ` ` `int` `sum = ` `0` `;` ` ` `// Temporarily store x` ` ` `int` `temp = x;` ` ` `// Calculate sum` ` ` `// of digits of x` ` ` `while` `(x != ` `0` `) {` ` ` `sum += x % ` `10` `;` ` ` `x /= ` `10` `;` ` ` `}` ` ` `// If x is not divisible by sum` ` ` `if` `(temp % sum != ` `0` `)` ` ` `return` `false` `;` ` ` `// Otherwise` ` ` `else` ` ` `return` `true` `;` ` ` `}` ` ` `// Function to perform` ` ` `// the precomputation` ` ` `static` `void` `precompute()` ` ` `{` ` ` ` ` `// Iterate from i equals 1 to 1e5` ` ` `for` `(` `int` `i = ` `1` `; i <= ` `100000` `; i++) {` ` ` ` ` `// Check if i is divisible` ` ` `// by sum of its digits` ` ` `if` `(isDivisible(i))` ` ` `arr[i] = ` `1` `;` ` ` `else` ` ` `arr[i] = ` `0` `;` ` ` `}` ` ` `// Convert arr[] to prefix sum array` ` ` `for` `(` `int` `i = ` `1` `; i <= ` `100000` `; i++) {` ` ` `arr[i] = arr[i] + arr[i - ` `1` `];` ` ` `}` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `// Given queries` ` ` `int` `Q[][] = { { ` `5` `, ` `9` `}, { ` `5` `, ` `20` `} };` ` ` `precompute();` ` ` `for` `(` `int` `q[] : Q) {` ` ` `// Using inclusion-exclusion` ` ` `// principle, calculate the result` ` ` `System.out.println(arr[q[` `1` `]] - arr[q[` `0` `] - ` `1` `]);` ` ` `}` ` ` `}` `}` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `static` `int` `[]arr = ` `new` `int` `[100005];` `// Function to check if the number x` `// is divisible by its sum of digits` `static` `bool` `isDivisible(` `int` `x)` `{` ` ` ` ` `// Stores sum of digits of x` ` ` `int` `sum = 0;` ` ` `// Temporarily store x` ` ` `int` `temp = x;` ` ` `// Calculate sum` ` ` `// of digits of x` ` ` `while` `(x != 0)` ` ` `{` ` ` `sum += x % 10;` ` ` `x /= 10;` ` ` `}` ` ` `// If x is not divisible by sum` ` ` `if` `(temp % sum != 0)` ` ` `return` `false` `;` ` ` `// Otherwise` ` ` `else` ` ` `return` `true` `;` `}` `// Function to perform` `// the precomputation` `static` `void` `precompute()` `{` ` ` ` ` `// Iterate from i equals 1 to 1e5` ` ` `for` `(` `int` `i = 1; i <= 100000; i++)` ` ` `{` ` ` ` ` `// Check if i is divisible` ` ` `// by sum of its digits` ` ` `if` `(isDivisible(i))` ` ` `arr[i] = 1;` ` ` `else` ` ` `arr[i] = 0;` ` ` `}` ` ` `// Convert []arr to prefix sum array` ` ` `for` `(` `int` `i = 1; i <= 100000; i++)` ` ` `{` ` ` `arr[i] = arr[i] + arr[i - 1];` ` ` `}` `}` `public` `static` `int` `[] GetRow(` `int` `[,] matrix, ` `int` `row)` `{` ` ` `var` `rowLength = matrix.GetLength(1);` ` ` `var` `rowVector = ` `new` `int` `[rowLength];` ` ` ` ` `for` `(` `var` `i = 0; i < rowLength; i++)` ` ` `rowVector[i] = matrix[row, i];` ` ` ` ` `return` `rowVector;` `}` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` ` ` `// Given queries` ` ` `int` `[,]Q = { { 5, 9 }, { 5, 20 } };` ` ` `int` `[]q;` ` ` `precompute();` ` ` ` ` `for` `(` `int` `i = 0; i < Q.GetLength(0); i++)` ` ` `{` ` ` `q = GetRow(Q,i);` ` ` ` ` `// Using inclusion-exclusion` ` ` `// principle, calculate the result` ` ` `Console.WriteLine(arr[q[1]] - arr[q[0] - 1]);` ` ` `}` `}` `}` `// This code is contributed by shikhasingrajput` |

**Output:**

5 9

**Time Complexity:** O(N)**Auxiliary Space:** O(maxm), where **maxm** denotes the maximum value of R.