Count numbers divisible by K in a range with Fibonacci digit sum for Q queries
Given an array arr[][] containing Q queries and an integer K where each query consists of a range [L, R], the task is to find the count of integers in the given range whose digit sum is a Fibonacci number and divisible by K.
Examples:
Input: arr[][] = { {1, 11}, {5, 15}, {2, 24} }, K = 2
Output: 3 2 5
Explanation:
For query 1: 2, 8 and 11 are the numbers in the given range whose digit sum is Fibonacci and divisible by K.
For query 2: 8 and 11 are the numbers in the given range whose digit sum is Fibonacci and divisible by K.
For query 3: 2, 8, 11, 17 and 20 are the numbers in the given range whose digit sum is Fibonacci and divisible by K.
Input: arr[][] = { {2, 17}, {3, 24} }, K = 3
Output: 4 4
Explanation:
For query 1: 2, 8, 11 and 17 are the numbers in the given range whose digit sum is Fibonacci and divisible by K.
For query 2: 8, 11, 17 and 20 are the numbers in the given range whose digit sum is Fibonacci and divisible by K.
Approach: The idea is to use hashing to precompute and store the Fibonacci nodes up to the maximum value in the given range, to make the checking easy and efficient (in O(1) time).
- After precomputation, mark all the integers from 1 to maxVal which are divisible by K and are fibonacci.
- Find the prefix sum of the marked array.
- Answer the given queries by prefix[right] – prefix[left – 1].
Below is the implementation of the above approach:
C++
// C++ program to count the integers // in a range [L, R] such that // their digit sum is Fibonacci // and divisible by K #include <bits/stdc++.h> using namespace std; const int maxSize = 1e5 + 5; bool isFib[maxSize]; int prefix[maxSize]; // Function to return the // digit sum of a number int digitSum( int num) { int s = 0; while (num != 0) { s = s + num % 10; num = num / 10; } return s; } // Function to generate all the Fibonacci // numbers upto maxSize void generateFibonacci() { memset (isFib, false , sizeof (isFib)); // Adding the first two Fibonacci // numbers in the set int prev = 0, curr = 1; isFib[prev] = isFib[curr] = true ; // Computing the remaining Fibonacci // numbers based on the previous // two Fibonacci numbers while (curr < maxSize) { int temp = curr + prev; isFib[temp] = true ; prev = curr; curr = temp; } } // Pre-Computation till maxSize // and for a given K void precompute( int k) { generateFibonacci(); for ( int i = 1; i < maxSize; i++) { // Getting the digit sum int sum = digitSum(i); // Check if the digit sum // is Fibonacci and divisible by k if (isFib[sum] == true && sum % k == 0) { prefix[i]++; } } // Taking Prefix Sum for ( int i = 1; i < maxSize; i++) { prefix[i] = prefix[i] + prefix[i - 1]; } } // Function to perform the queries void performQueries( int k, int q, vector<vector< int > >& query) { // Precompute the results precompute(k); vector< int > ans; // Iterating through the queries for ( int i = 0; i < q; i++) { int l = query[i][0], r = query[i][1]; // Getting count of range // in range [L, R] int cnt = prefix[r] - prefix[l - 1]; cout << cnt << endl; } } // Driver code int main() { vector<vector< int > > query = { { 1, 11 }, { 5, 15 }, { 2, 24 } }; int k = 2, q = query.size(); performQueries(k, q, query); return 0; } |
Java
// Java program to count the integers // in a range [L, R] such that // their digit sum is Fibonacci // and divisible by K import java.util.*; class GFG{ static int maxSize = ( int ) (1e5 + 5 ); static boolean []isFib = new boolean [maxSize]; static int []prefix = new int [maxSize]; // Function to return the // digit sum of a number static int digitSum( int num) { int s = 0 ; while (num != 0 ) { s = s + num % 10 ; num = num / 10 ; } return s; } // Function to generate all the Fibonacci // numbers upto maxSize static void generateFibonacci() { Arrays.fill(isFib, false ); // Adding the first two Fibonacci // numbers in the set int prev = 0 , curr = 1 ; isFib[prev] = isFib[curr] = true ; // Computing the remaining Fibonacci // numbers based on the previous // two Fibonacci numbers while (curr < maxSize) { int temp = curr + prev; if (temp < maxSize) isFib[temp] = true ; prev = curr; curr = temp; } } // Pre-Computation till maxSize // and for a given K static void precompute( int k) { generateFibonacci(); for ( int i = 1 ; i < maxSize; i++) { // Getting the digit sum int sum = digitSum(i); // Check if the digit sum // is Fibonacci and divisible by k if (isFib[sum] == true && sum % k == 0 ) { prefix[i]++; } } // Taking Prefix Sum for ( int i = 1 ; i < maxSize; i++) { prefix[i] = prefix[i] + prefix[i - 1 ]; } } // Function to perform the queries static void performQueries( int k, int q, int [][] query) { // Precompute the results precompute(k); // Iterating through the queries for ( int i = 0 ; i < q; i++) { int l = query[i][ 0 ], r = query[i][ 1 ]; // Getting count of range // in range [L, R] int cnt = prefix[r] - prefix[l - 1 ]; System.out.print(cnt + "\n" ); } } // Driver code public static void main(String[] args) { int [][]query = { { 1 , 11 }, { 5 , 15 }, { 2 , 24 } }; int k = 2 , q = query.length; performQueries(k, q, query); } } // This code is contributed by Princi Singh |
Python3
# Python 3 program to count the integers # in a range [L, R] such that # their digit sum is Fibonacci # and divisible by K maxSize = 100005 isFib = [ False ] * (maxSize) prefix = [ 0 ] * maxSize # Function to return the # digit sum of a number def digitSum(num): s = 0 while (num ! = 0 ): s = s + num % 10 num = num / / 10 return s # Function to generate all the Fibonacci # numbers upto maxSize def generateFibonacci(): global isFib # Adding the first two Fibonacci # numbers in the set prev = 0 curr = 1 isFib[prev] = True isFib[curr] = True # Computing the remaining Fibonacci # numbers based on the previous # two Fibonacci numbers while (curr < maxSize): temp = curr + prev if temp < maxSize: isFib[temp] = True prev = curr curr = temp # Pre-Computation till maxSize # and for a given K def precompute(k): generateFibonacci() global prefix for i in range ( 1 , maxSize): # Getting the digit sum sum = digitSum(i) # Check if the digit sum # is Fibonacci and divisible by k if (isFib[ sum ] = = True and sum % k = = 0 ): prefix[i] + = 1 # Taking Prefix Sum for i in range ( 1 , maxSize): prefix[i] = prefix[i] + prefix[i - 1 ] # Function to perform the queries def performQueries(k, q,query): # Precompute the results precompute(k) # Iterating through the queries for i in range (q): l = query[i][ 0 ] r = query[i][ 1 ] # Getting count of range # in range [L, R] cnt = prefix[r] - prefix[l - 1 ] print (cnt) # Driver code if __name__ = = "__main__" : query = [ [ 1 , 11 ], [ 5 , 15 ], [ 2 , 24 ] ] k = 2 q = len (query) performQueries(k, q, query) # This code is contributed by chitranayal |
C#
// C# program to count the integers // in a range [L, R] such that // their digit sum is Fibonacci // and divisible by K using System; class GFG{ static int maxSize = ( int ) (1e5 + 5); static bool []isFib = new bool [maxSize]; static int []prefix = new int [maxSize]; // Function to return the // digit sum of a number static int digitSum( int num) { int s = 0; while (num != 0) { s = s + num % 10; num = num / 10; } return s; } // Function to generate all the Fibonacci // numbers upto maxSize static void generateFibonacci() { // Adding the first two Fibonacci // numbers in the set int prev = 0, curr = 1; isFib[prev] = isFib[curr] = true ; // Computing the remaining Fibonacci // numbers based on the previous // two Fibonacci numbers while (curr < maxSize) { int temp = curr + prev; if (temp < maxSize) isFib[temp] = true ; prev = curr; curr = temp; } } // Pre-Computation till maxSize // and for a given K static void precompute( int k) { generateFibonacci(); for ( int i = 1; i < maxSize; i++) { // Getting the digit sum int sum = digitSum(i); // Check if the digit sum // is Fibonacci and divisible by k if (isFib[sum] == true && sum % k == 0) { prefix[i]++; } } // Taking Prefix Sum for ( int i = 1; i < maxSize; i++) { prefix[i] = prefix[i] + prefix[i - 1]; } } // Function to perform the queries static void performQueries( int k, int q, int [,] query) { // Precompute the results precompute(k); // Iterating through the queries for ( int i = 0; i < q; i++) { int l = query[i, 0], r = query[i, 1]; // Getting count of range // in range [L, R] int cnt = prefix[r] - prefix[l - 1]; Console.Write(cnt + "\n" ); } } // Driver code public static void Main(String[] args) { int [,]query = { { 1, 11 }, { 5, 15 }, { 2, 24 } }; int k = 2, q = query.GetLength(0); performQueries(k, q, query); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to count the integers // in a range [L, R] such that // their digit sum is Fibonacci // and divisible by K let maxSize = (1e5 + 5); let isFib = Array.from({length: maxSize}, (_, i) => 0); let prefix = Array.from({length: maxSize}, (_, i) => 0); // Function to return the // digit sum of a number function digitSum(num) { let s = 0; while (num != 0) { s = s + num % 10; num = Math.floor(num / 10); } return s; } // Function to generate all the Fibonacci // numbers upto maxSize function generateFibonacci() { isFib = Array.from({length: maxSize}, (_, i) => false ); // Adding the first two Fibonacci // numbers in the set let prev = 0, curr = 1; isFib[prev] = isFib[curr] = true ; // Computing the remaining Fibonacci // numbers based on the previous // two Fibonacci numbers while (curr < maxSize) { let temp = curr + prev; if (temp < maxSize) isFib[temp] = true ; prev = curr; curr = temp; } } // Pre-Computation till maxSize // and for a given K function precompute(k) { generateFibonacci(); for (let i = 1; i < maxSize; i++) { // Getting the digit sum let sum = digitSum(i); // Check if the digit sum // is Fibonacci and divisible by k if (isFib[sum] == true && sum % k == 0) { prefix[i]++; } } // Taking Prefix Sum for (let i = 1; i < maxSize; i++) { prefix[i] = prefix[i] + prefix[i - 1]; } } // Function to perform the queries function performQueries( k, q, query) { // Precompute the results precompute(k); // Iterating through the queries for (let i = 0; i < q; i++) { let l = query[i][0], r = query[i][1]; // Getting count of range // in range [L, R] let cnt = prefix[r] - prefix[l - 1]; document.write(cnt + "<br/>" ); } } // Driver code let query = [[ 1, 11 ], [ 5, 15 ], [ 2, 24 ]]; let k = 2, q = query.length; performQueries(k, q, query); // This code is contributed by sanjoy_62. </script> |
3 2 5
Time Complexity: O(maxSize,q)
Auxiliary Space: O(maxSize)