Given a 2D array arr[][] with each row of the form of a query { L, R }, the task is to count the numbers in the range [L, R] such that the number is divisible by all of its non-zero digit.
Examples:
Input: arr[][] ={ {1, 5}, {12, 14} }
Output: 5 1
Explanation:
Query1: All the numbers in the range [1, 5] are divisible by their digits.
Query2: Numbers in the range [12, 14] which are divisible by all of its digits is 12 only.Input: arr[][] = { {1, 20} }
Output:14
Explanation:
Numbers in the range [1, 20] which are divisible by all of its non-zero digits are: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 20}
Naive Approach: The simplest approach to solve this problem is to traverse the array arr[][] and for every ith row of the array, iterate over the range [L, R]. For every element in the range, check if the number is divisible by all of its non-zero digits or not. If found to be true, then increment the count. Finally, print the count obtained.
Time Complexity: O(N * (R – L)), where N is the count of rows
Auxiliary Space: O(1)
Efficient approach: The above approach can be optimized by finding the maximum possible value of arr[i][1] and precompute the count of numbers which is divisible by its non-zero digits using Prefix Sum technique. Follow the steps below to solve the problem:
- Initialize a variable, say Max, to store the maximum possible value of arr[i][1].
- Initialize an array, say prefCntDiv[], where prefCntDiv[i] stores the count of numbers from the range [1, i] which is divisible by its non-zero digits.
- Iterate over the range [1, Max]. For every ith iteration, check if i is divisible by all of its non-zero digits or not. If found to be true, then update prefCntDiv[i] = prefCntDiv[i – 1] + 1.
- Otherwise, update prefCntDiv[i] = prefCntDiv[i – 1].
- Traverse the array arr[]. For every ith row of the array, print prefCntDiv[arr[i][1]] – prefCntDiv[arr[i][0] – 1].
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define Max 1000005// Function to check if a number is divisible// by all of its non-zero digits or notbool CheckDivByAllDigits(int number){ // Stores the number int n = number; // Iterate over the digits // of the numbers while (n > 0) { // If digit of number // is non-zero if (n % 10) // If number is not divisible // by its current digit if (number % (n % 10)) { return false; } // Update n n /= 10; } return true;}// Function to count of numbers which are// divisible by all of its non-zero// digits in the range [1, i]void cntNumInRang(int arr[][2], int N){ // Stores count of numbers which are // divisible by all of its non-zero // digits in the range [1, i] int prefCntDiv[Max] = { 0 }; // Iterate over the range [1, Max] for (int i = 1; i <= Max; i++) { // Update prefCntDiv[i] = prefCntDiv[i - 1] + (CheckDivByAllDigits(i)); } // Traverse the array, arr[] for (int i = 0; i < N; i++) cout << (prefCntDiv[arr[i][1]] - prefCntDiv[arr[i][0] - 1]) << " ";}// Driver Codeint main(){ int arr[][2] = { { 1, 5 }, { 12, 14 } }; int N = sizeof(arr) / sizeof(arr[0]); cntNumInRang(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{ public static int Max = 1000005; // Function to check if a number is divisible // by all of its non-zero digits or not static boolean CheckDivByAllDigits(int number) { // Stores the number int n = number; // Iterate over the digits // of the numbers while (n > 0) { // If digit of number // is non-zero if (n % 10 != 0) // If number is not divisible // by its current digit if (number % (n % 10) != 0) { return false; } // Update n n /= 10; } return true; } // Function to count of numbers which are // divisible by all of its non-zero // digits in the range [1, i] static void cntNumInRang(int arr[][], int N) { // Stores count of numbers which are // divisible by all of its non-zero // digits in the range [1, i] int prefCntDiv[] = new int[Max + 1]; // Iterate over the range [1, Max] for (int i = 1; i <= Max; i++) { int ans = 0; if (CheckDivByAllDigits(i)) ans = 1; // Update prefCntDiv[i] = prefCntDiv[i - 1] + ans; } // Traverse the array, arr[] for (int i = 0; i < N; i++) System.out.print((prefCntDiv[arr[i][1]] - prefCntDiv[arr[i][0] - 1]) + " "); } // Driver Code public static void main(String[] args) { int arr[][] = { { 1, 5 }, { 12, 14 } }; int N = arr.length; cntNumInRang(arr, N); }}// This code is contributed by Dharanendra L V |
Python3
# Python3 program to implement# the above approach# Function to check if a number is divisible# by all of its non-zero digits or notdef CheckDivByAllDigits(number): # Stores the number n = number # Iterate over the digits # of the numbers while (n > 0): # If digit of number # is non-zero if (n % 10): # If number is not divisible # by its current digit if (number % (n % 10)): return False # Update n n //= 10 return True# Function to count of numbers which are# divisible by all of its non-zero# digits in the range [1, i]def cntNumInRang(arr, N): global Max # Stores count of numbers which are # divisible by all of its non-zero # digits in the range [1, i] prefCntDiv = [0]*Max # Iterate over the range [1, Max] for i in range(1, Max): # Update prefCntDiv[i] = prefCntDiv[i - 1] + (CheckDivByAllDigits(i)) # Traverse the array, arr[] for i in range(N): print(prefCntDiv[arr[i][1]]- prefCntDiv[arr[i][0] - 1], end = " ")# Driver Codeif __name__ == '__main__': arr =[ [ 1, 5 ], [12, 14]] Max = 1000005 N = len(arr) cntNumInRang(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# program to implement// the above approachusing System;class GFG{ public static int Max = 1000005; // Function to check if a number is divisible // by all of its non-zero digits or not static bool CheckDivByAllDigits(int number) { // Stores the number int n = number; // Iterate over the digits // of the numbers while (n > 0) { // If digit of number // is non-zero if (n % 10 != 0) // If number is not divisible // by its current digit if (number % (n % 10) != 0) { return false; } // Update n n /= 10; } return true; } // Function to count of numbers which are // divisible by all of its non-zero // digits in the range [1, i] static void cntNumInRang(int[, ] arr, int N) { // Stores count of numbers which are // divisible by all of its non-zero // digits in the range [1, i] int[] prefCntDiv = new int[Max + 1]; // Iterate over the range [1, Max] for (int i = 1; i <= Max; i++) { int ans = 0; if (CheckDivByAllDigits(i)) ans = 1; // Update prefCntDiv[i] = prefCntDiv[i - 1] + ans; } // Traverse the array, arr[] for (int i = 0; i < N; i++) Console.Write((prefCntDiv[arr[i, 1]] - prefCntDiv[arr[i, 0] - 1]) + " "); } // Driver Code public static void Main(string[] args) { int[, ] arr = { { 1, 5 }, { 12, 14 } }; int N = arr.GetLength(0); cntNumInRang(arr, N); }}// This code is contributed by chitranayal. |
Javascript
<script>// Javascript program to implement// the above approachconst Max = 1000005;// Function to check if a number is divisible// by all of its non-zero digits or notfunction CheckDivByAllDigits(number){ // Stores the number let n = number; // Iterate over the digits // of the numbers while (n > 0) { // If digit of number // is non-zero if (n % 10) // If number is not divisible // by its current digit if (number % (n % 10)) { return false; } // Update n n = parseInt(n / 10); } return true;}// Function to count of numbers which are// divisible by all of its non-zero// digits in the range [1, i]function cntNumInRang(arr, N){ // Stores count of numbers which are // divisible by all of its non-zero // digits in the range [1, i] let prefCntDiv = new Array(Max).fill(0); // Iterate over the range [1, Max] for (let i = 1; i <= Max; i++) { // Update prefCntDiv[i] = prefCntDiv[i - 1] + (CheckDivByAllDigits(i)); } // Traverse the array, arr[] for (let i = 0; i < N; i++) document.write((prefCntDiv[arr[i][1]] - prefCntDiv[arr[i][0] - 1]) + " ");}// Driver Code let arr = [ [ 1, 5 ], [ 12, 14 ] ]; let N = arr.length; cntNumInRang(arr, N);</script> |
Output:
5 1
Time Complexity: O(N + Max), where Max is the maximum value of arr[i][1]
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
