Given an array arr[] consisting of N elements and an arrayQ[], the task for each query is to find the length of the longest prefix such that all the elements of this prefix are divisible by K.
Examples:
Input: arr[] = {12, 6, 15, 3, 10}, Q[] = {4, 3, 2}
Output: 1 4 2
Explanation:
- Q[0] = 4: arr[0] (= 12) is divisible by 4. arr[1] is not divisible by 4. Therefore, the length of the longest prefix divisible by 4 is 1.
- Q[1] = 3: The longest prefix which is divisible by 3 is {12, 6, 15, 3}. Therefore, print 4 as the required output.
- Q[2] = 2: The longest prefix which is divisible by 2 is {12, 6}.
Input: arr[] = {4, 3, 2, 1}, Q[] = {1, 2, 3}
Output: 4 1 0
Approach: The idea is to observe that if the first i elements of the array are divisible by the given integer K, then their GCD will also be divisible by K. Follow the steps below to solve the problem:
- Before finding the answer to each query, pre-compute the gcd of the prefixes of the array in another array g[] such that g[0] = arr[0] and for the rest of the elements g[i] = GCD(arr[i], g[i – 1]).
- Then, for each element in the array Q[], perform Binary Search on the array g[] and find the last index of g[] which is divisible by Q[i].
- It has to be noted that all the elements in this index will be divisible by K, since the gcd of all the elements till this index is divisible by K.
- Print the length of the longest prefix.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find index of the last// element which is divisible the given elementint binSearch(int* g, int st, int en, int val){ // Initially assume the // index to be -1 int ind = -1; while (st <= en) { // Find the mid element // of the subarray int mid = st + (en - st) / 2; // If the mid element is divisible by // given element, then move to right // of mid and update ind to mid if (g[mid] % val == 0) { ind = mid; st = mid + 1; } // Otherwise, move to left of mid else { en = mid - 1; } } // Return the length of prefix return ind + 1;}// Function to compute and print for each queryvoid solveQueries(int* arr, int* queries, int n, int q){ int g[n]; // Pre compute the gcd of the prefixes // of the input array in the array g[] for (int i = 0; i < n; i++) { if (i == 0) { g[i] = arr[i]; } else { g[i] = __gcd(g[i - 1], arr[i]); } } // Perform binary search // for each query for (int i = 0; i < q; i++) { cout << binSearch(g, 0, n - 1, queries[i]) << " "; }}// Driver Codeint main(){ // Given array int arr[] = { 12, 6, 15, 3, 10 }; // Size of array int n = sizeof(arr) / sizeof(arr[0]); // Given Queries int queries[] = { 4, 3, 2 }; // Size of queries int q = sizeof(queries) / sizeof(queries[0]); solveQueries(arr, queries, n, q);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find index of the last// element which is divisible the given elementstatic int binSearch(int[] g, int st, int en, int val){ // Initially assume the // index to be -1 int ind = -1; while (st <= en) { // Find the mid element // of the subarray int mid = st + (en - st) / 2; // If the mid element is divisible by // given element, then move to right // of mid and update ind to mid if (g[mid] % val == 0) { ind = mid; st = mid + 1; } // Otherwise, move to left of mid else { en = mid - 1; } } // Return the length of prefix return ind + 1;}// Function to compute and print for each querystatic void solveQueries(int []arr, int []queries, int n, int q){ int []g = new int[n]; // Pre compute the gcd of the prefixes // of the input array in the array g[] for (int i = 0; i < n; i++) { if (i == 0) { g[i] = arr[i]; } else { g[i] = __gcd(g[i - 1], arr[i]); } } // Perform binary search // for each query for (int i = 0; i < q; i++) { System.out.print(binSearch(g, 0, n - 1, queries[i]) + " "); }}static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); } // Driver Codepublic static void main(String[] args){ // Given array int arr[] = { 12, 6, 15, 3, 10 }; // Size of array int n = arr.length; // Given Queries int queries[] = { 4, 3, 2 }; // Size of queries int q = queries.length; solveQueries(arr, queries, n, q);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachfrom math import gcd as __gcd# Function to find index of the last# element which is divisible the # given elementdef binSearch(g, st, en, val): # Initially assume the # index to be -1 ind = -1 while (st <= en): # Find the mid element # of the subarray mid = st + (en - st) // 2 # If the mid element is divisible by # given element, then move to right # of mid and update ind to mid if (g[mid] % val == 0): ind = mid st = mid + 1 # Otherwise, move to left of mid else: en = mid - 1 # Return the length of prefix return ind + 1# Function to compute and print for each querydef solveQueries(arr, queries, n, q): g = [0 for i in range(n)] # Pre compute the gcd of the prefixes # of the input array in the array g[] for i in range(n): if (i == 0): g[i] = arr[i] else: g[i] = __gcd(g[i - 1], arr[i]) # Perform binary search # for each query for i in range(q): print(binSearch(g, 0, n - 1, queries[i]), end = " ")# Driver Codeif __name__ == '__main__': # Given array arr = [ 12, 6, 15, 3, 10 ] # Size of array n = len(arr) # Given Queries queries = [ 4, 3, 2 ] # Size of queries q = len(queries) solveQueries(arr, queries, n, q)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approach using System; class GFG{ // Function to find index of the last// element which is divisible the given elementstatic int binSearch(int[] g, int st, int en, int val){ // Initially assume the // index to be -1 int ind = -1; while (st <= en) { // Find the mid element // of the subarray int mid = st + (en - st) / 2; // If the mid element is divisible by // given element, then move to right // of mid and update ind to mid if (g[mid] % val == 0) { ind = mid; st = mid + 1; } // Otherwise, move to left of mid else { en = mid - 1; } } // Return the length of prefix return ind + 1;} // Recursive function to return // gcd of a and b static int gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a - b, b); return gcd(a, b - a); } // Function to compute and print for each query static void solveQueries(int[] arr, int[] queries, int n, int q) { int[] g = new int[n]; // Pre compute the gcd of the prefixes // of the input array in the array g[] for (int i = 0; i < n; i++) { if (i == 0) { g[i] = arr[i]; } else { g[i] = gcd(g[i - 1], arr[i]); } } // Perform binary search // for each query for (int i = 0; i < q; i++) { Console.Write(binSearch(g, 0, n - 1, queries[i]) + " "); } } // Driver codepublic static void Main(){ // Given array int[] arr = { 12, 6, 15, 3, 10 }; // Size of array int n = arr.Length; // Given Queries int[] queries = { 4, 3, 2 }; // Size of queries int q = queries.Length; solveQueries(arr, queries, n, q);}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>//Javascript program for the above approach//function for GCDfunction __gcd( a, b) { return b == 0? a:__gcd(b, a % b); }// Function to find index of the last// element which is divisible the given elementfunction binSearch(g, st, en, val){ // Initially assume the // index to be -1 var ind = -1; while (st <= en) { // Find the mid element // of the subarray var mid = st + parseInt((en - st) / 2); // If the mid element is divisible by // given element, then move to right // of mid and update ind to mid if (g[mid] % val == 0) { ind = mid; st = mid + 1; } // Otherwise, move to left of mid else { en = mid - 1; } } // Return the length of prefix return ind + 1;}// Function to compute and print for each queryfunction solveQueries(arr, queries, n, q){ var g = new Array(n); // Pre compute the gcd of the prefixes // of the input array in the array g[] for (var i = 0; i < n; i++) { if (i == 0) { g[i] = arr[i]; } else { g[i] = __gcd(g[i - 1], arr[i]); } } // Perform binary search // for each query for (var i = 0; i < q; i++) { document.write( binSearch(g, 0, n - 1, queries[i]) + " "); }}var arr = [ 12, 6, 15, 3, 10 ];// Size of arrayvar n = arr.length;// Given Queriesvar queries = [ 4, 3, 2 ];// Size of queriesvar q = queries.length;solveQueries(arr, queries, n, q);//This code is contributed by SoumikMondal</script> |
Output:
1 4 2
Time Complexity: O(NlogN + QlogN)
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!
