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:
Input: Q[][]= {{5, 9}, {5, 20}}
Output:
5
9
Explanation:
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
0
Explanation:
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 ith index, the count of numbers up to i which are divisible by the sum of their digits.
- Iterate over the range [1, 105] using a variable, say i, and for every ith 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.
- 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 digitsbool 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 precomputationvoid 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 codeint 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 approachimport 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]); } }} |
Python3
# Python program for the above approacharr = [0] * 100005# Function to check if the number x# is divisible by its sum of digitsdef isDivisible(x): # Stores sum of digits of x sum = 0; # Temporarily store x temp = x; # Calculate sum # of digits of x while (x != 0): sum += x % 10; x = x // 10; # If x is not divisible by sum if (temp % sum != 0): return False; # Otherwise else: return True;# Function to perform# the precomputationdef precompute(): # Iterate from i equals 1 to 1e5 for i in range(1, 100000 + 1): # 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 i in range(1, 100000 + 1): arr[i] = arr[i] + arr[i - 1]; # Driver Code# Given queriesQ = [[5, 9], [5, 20]];precompute();for q in Q: # Using inclusion-exclusion # principle, calculate the result print(arr[q[1]] - arr[q[0] - 1]);# This code is contributed by saurabh_jaiswal. |
C#
// C# program for the above approachusing System;class GFG{static int []arr = new int[100005];// Function to check if the number x// is divisible by its sum of digitsstatic 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 precomputationstatic 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 Codepublic 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 |
Javascript
<script>// Javascript program for the above approachlet arr = new Array(100005).fill(0);// Function to check if the number x// is divisible by its sum of digitsfunction isDivisible(x) { // Stores sum of digits of x let sum = 0; // Temporarily store x let temp = x; // Calculate sum // of digits of x while (x != 0) { sum += x % 10; x = Math.floor(x / 10); } // If x is not divisible by sum if (temp % sum != 0) return false; // Otherwise else return true;}// Function to perform// the precomputationfunction precompute() { // Iterate from i equals 1 to 1e5 for (let 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 (let i = 1; i <= 100000; i++) { arr[i] = arr[i] + arr[i - 1]; }}// Driver Code// Given querieslet Q = [[5, 9], [5, 20]];precompute();for (let q of Q){ // Using inclusion-exclusion // principle, calculate the result document.write(arr[q[1]] - arr[q[0] - 1] + " <br>");}// This code is contributed by saurabh_jaiswal.</script> |
Output:
5 9
Time Complexity: O(N)
Auxiliary Space: O(maxm), where maxm denotes the maximum value of R.
