Please read the new rule regarding the restriction on the use of AI tools. ×

I_am_Noobieee's blog

By I_am_Noobieee, history, 3 weeks ago, In English

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.

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the leetcode problem with small constraints

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot. Really appreciate it :D

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Welcome ^^

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 Step

        We 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.