I have an array of n positive integers. I want to calculate a list of all contiguous subarray products of size k modulo p. For instance for the following array:

a = [3, 12, 5, 2, 3, 7, 4, 3]

with k = 3 and p = 12, the ordered list of all k-sized contiguous subarray products will be:

k_products = [180, 120, 30, 42, 84, 84]

and modulo p we have:

k_products_p = [0, 0, 6, 6, 0, 0]

we can easily compute k_products using a sliding window. All we have to do is to compute the product for the first k-sized subarray and then compute the next elements of k_product using the following formula:

k_product[i] = k_product[i - 1] * a[i k] / a[i - 1]

and after forming the whole list, we can compute k_product[i] % p for each i to get k_product_p. That's it. O(n) complexity is pretty good.

But if the elements of a[i] are big, the elements of k_product may overflow, and thus we cannot compute k_product_p. Plus, we cannot, for example do the following:

k_product[i] = ((k_product[i - 1] % p) * (a[i k] % p) / (a[i - 1] % p)) % p // incorrect

So is there a fast algorithm to do this? Note that p is not necessarily prime and it is also not necessarily coprime to the elements of a.

Edit: As mentioned in the comments, there will be no overflow in python, but working with very big numbers will be time-consuming.

CodePudding user response：

This is not a sliding window algorithm, but it is a simple and effective way to solve this problem in O(n) time without any division:

Let A be your original array. We will imagine that there is a "mark" on every kth element of A -- elements A[0], A[k], A[2k], etc. This ensures that every k-length window in A will contain exactly one mark.

Now, make two new arrays B and C, such that:

• In array B, each element B[i] will contain the product (mod p) of A[i] and all following elements up to but not including the next mark. If A[i] is marked, then B[i] = 1. You can calculate this in a single pass backward from i=n-1 to i=0.

• In array C, each element C[i] will contain the product (mod p) of A[i] and all preceding elements down to and including the previous mark. If A[i] is marked, then C[i] = A[i]. You can calculate this in a single pass forward from i=0 to i=n-1.

Now, you can easily calculate the complete product of any k-length window in constant time, because the product of any window from A[i]...A[i k-1] is just B[i] * C[i k-1]. Remember that there is exactly one mark inside the window. B[i] is the product of the elements before the mark, and C[i k-1] is the product of the marked element and the elements after it.