Count number of subarrays whose product is not divisible by k

Question

Given an array, I want to count the number of subarrays (contiguous) who's product when taken will not be divisible by k.

Eg. Let A = [1, 2, 3, 4, 5, 6] and K = 2

Then the number of subarrays such that the product is not divisible by K is 2:

{1}
{3}
{5}

Rest of them are all divisible by 2.

{1, 2}
{1, 2, 3}
{1, 2, 3, 4}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}
{2}
{2, 3}
{2, 3, 4}
{2, 3, 4, 5} etc..

I tried first calculating the total number of subarrays (n)(n+1)/2 and then subtracting the number of subarrays that are divisible by k by using mod but it doesn't work. How do I get around this one?

This calculates (wrongly) number of subarrays who's product is divisible by K:

int curr = 1;
    int x = 0;
    for (int i = 0; i < a.length; i++) {
        curr = curr * a[i] % k;
        if (curr == 0) {
            curr = 1;
            if (x > 0)
                ans = ans.subtract(NumberUtils.nChooseR(x + 1, 2));
            if (a[i] % k != 0) {
                x = 1;
            } else {
                x = 0;
            }
        } else {
            x++;
        }
    }
    if (x != 0) {
        ans = ans.subtract(NumberUtils.nChooseR(x + 1, 2));
    }
    return ans;

A slightly related question is this one but it involves addition so it cannot be applied here.

Edit : constraints on array size is 10^5 and on array elements is 10^9. Hence, I'm looking for solution in linear or linearithmic time

What is *subarray*? Should it contain *one item only*? If not, why `{3, 5}` is not a solution? — Dmitry Bychenko, Nov 21 '16 at 11:58
What is the solution in case `K = 4`? `{1}, {2}, {3, {5}` or `{1}, {3}, {5}, {6}`? — Dmitry Bychenko, Nov 21 '16 at 11:59
@DmitryBychenko by subarray I mean contiguous set of elements — Mayur Kulkarni, Nov 21 '16 at 12:01
What is subarray's *production*? E.g. what is `{1, 3} x {5, 7}`? — Dmitry Bychenko, Nov 21 '16 at 12:01
@DmitryBychenko Im not sure what you mean by production, but incase if you're asking how I'm multiplying these elements, is like this : if an array is : [3, 5, 8] and K is 2, then it's value is 3x5x8 = 120 which is divisible by 2, which means this is a valid subarray. On the other hand, if array = [1, 7, 11] its value is 77 which is not divisible by 2, so it's an invalid subarray — Mayur Kulkarni, Nov 21 '16 at 12:05
You have to obtain combinations of items. You should have `2^n-1` sub arrays (excluding the empty one) and then filter out the ones with items product modulo k is not zero. Generating the sub arrays is tricky. If you go the recursive way depending on your computer you may not even generate all sub arrays of a 23 or 24 item array. — Redu, Nov 21 '16 at 12:13
How large can N and K be? How fast do you need the solution to be? I can do it in N log N time if K^2 fits into the largest integer type. — kraskevich, Nov 21 '16 at 14:18

kraskevich · Accepted Answer · 2016-11-22T07:06:24.617

The "big picture":

It's easy to see that if the [l, r] subarray product is divisible by K, so is the product of [l, r + 1] and [l - 1, r].
Thus, if we could compute the value of the product of a subarray modulo K efficiently, we could just move two pointers (the left pointer goes right by exactly one and the right one keeps increasing until the product becomes equal to zero modulo K). This way, we would obtain the number of subarrays that start in the left pointer position and whose product is divisible by K. The answer would be just the sum over all values of the left pointer.
Problem: we can't store the product explicitly (it's too large). We can't do modulo arithmetic either as moving the left pointer would require modulo division. We may not have an inverse.

Solution 1:

Let's use a segment tree to compute the product modulo K of an arbitrary subarray in O(log N) time (we just build the tree and store the product of the corresponding range modulo K in each node. Now we just need to multiply these values (modulo K) for all nodes that a query range is decomposed into). We can use two pointers because we can compute the product of any subarray modulo K efficiently.

Solution 2:

Divide and conquer.

Let's split the array into two (almost) equal halves and solve the problem for each of them recursively. Now we just need to count the number of good subarrays that start in the first half and end in the second one. But the product of each such subarray is the product of the [l, m] and [m + 1, r] parts (all computation are done modulo K). But m is fixed (it's the position where the split the array). Thus, we can precompute the products of [l, m] for all l and the products of [m + 1, r] for all r in linear time. Now we can use two pointers again (they are initialized with 0 and m + 1, respectively). We can "merge" two halves in linear time, so the total time complexity is again O(N log N).

I think the segment tree idea will work, will implement and update you — Mayur Kulkarni, Nov 21 '16 at 15:37
In the two pointer approach, you say we need to use L and R and then decrement L by once and increment R until the product is divisible by K , where do initialise the pointers ? I'm not sure how this works and runs in less than n squared time can you elaborate? Edit : actually left pointer goes **right** once and the right pointer goes right until the product is 0 mod k. And also, once the answer is 0 mod k, you don't need to even increment the right pointer since the answer **will be 0** till the end of the array. Please edit this in the answer — Mayur Kulkarni, Nov 22 '16 at 06:42
The pointer algorithm was unfortunately too slow. But I later realised that moving left pointer once to the right was very ineffective. You should instead do this : while the product is **not** 0, rightpointer++, while the product **is** 0 rightPointer++ and ans = ans + size - rightPointer. The complete code is here : https://dpaste.de/XJhQ please include it in the answer to make it self contained. — Mayur Kulkarni, Nov 22 '16 at 10:40

Count number of subarrays whose product is not divisible by k

1 Answers1