You are given an array A of size N. You have to find the number of subarrays with gcd equal to K. Constraints : 1) 1 <= n <= 1e3 , 2) 0 <= A[i] <= 1e9 and 3) 1 <= K <= 1e9
I solved this question using brute force in O(N*N*log(N)) complexity. But I am just curious if there is any O(N*logN) solution to solve it. I have searched for sometime but could not find anything. Can someone pls tell if there is any way to do it O(N*logN)? Thanks.
Observe that the number of distinct gcd's in the contiguous subsequence of the given sequence a[] is going to be small. We can precompute for each distinct gcd its count and then store it in a map. There can be atmost log(max(nums)) distinct gcds in a subarray.
But how can I find all the distinct gcds possible in the array ? also if the array is like a = [1,2,3,4,5] should not there be 5 distinct gcds considering that gcd of subarray of length 1 is that element itself
This is the leetcode problem with small constraints
Yeah You can read (Link) https://leetcode.com/problems/number-of-subarrays-with-gcd-equal-to-k/solutions/2734123/o-n-log-max-nums-with-explanation-similar-question/
It is very well summarised and also you will be able to understand it.
Thanks a lot. Really appreciate it :D
Welcome ^^
If the Blog Ain't visible Here is the full proof.
O(N*log(max(nums)))
Observe that the number of distinct gcd's in the contiguous subsequence of the given sequence a[] is going to be small. We can precompute for each distinct gcd its count and then store it in a map. There can be atmost log(max(nums)) distinct gcds in a subarray.
How to get the count of each gcd ? Assume that we know the count of each gcd till a[i — 1]. A gcd of a subarray ending at a[i] will either be of the form gcd(a[i], <some subarray ending at a[i — 1]>) or will be a[i] itself. Since we already know the count of each distinct gcd ending at a[i — 1], we can simply take the gcd of all those with a[i] and increment the count of the resulting gcd (in the map that stores the count of subarrays ending at a[i]). We will need 2 maps, one to store the count of each gcd till a[i — 1], and one to calculate the count till a[i]. Finally we will need another map to store the final counts of each gcd. This map will be updated with the entries of the second map at the end of each iteration.
class Solution { public int subarrayGCD(int[] arr, int k) { int cnt = 0; Map<Integer,Integer> gcdEndingAtPrev = new HashMap<>(); //Stores all gcds ending at arr[i-1] with their frequncies if(arr[0] == k) cnt++; gcdEndingAtPrev.put(arr[0],1); for(int i=1;i<arr.length;i++){ HashMap<Integer,Integer> nf = new HashMap<>(); //Stores all gcds ending at arr[i]. This will become map for arr[i-1] on the next step int cur = arr[i]; gcdEndingAtPrev.put(cur,gcdEndingAtPrev.getOrDefault(cur,0)+1); //Important step. look below for explaination for(int key: gcdEndingAtPrev.keySet()){ //Iterate all prevoius gcds int cur_gcd = getGcd(key,cur); //Calculate gcd ending arr[i] int f = gcdEndingAtPrev.get(key); //Freq of new gcd is same as freq of previous gcd. If can't visualize this try a dry run with a sample array if(cur_gcd == k) cnt = cnt+f; nf.put(cur_gcd,nf.getOrDefault(cur_gcd,0)+f); } gcdEndingAtPrev = nf; } return cnt; } private static int getGcd(int a, int b){ if(a%b == 0) return b; return getGcd(b,a%b); } }Important StepWe increment the frequency of arr[i] in the map storing gcds ending at arr[i-1] because arr[i..i] is a valid subarray and shall be counted if its equal to k.