1

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.

Fish_n_Chips
  • 138
  • 4
  • in some instances it may help to first divide and then multiply – user1984 Oct 25 '21 at 10:26
  • In Python, there should be no `overflow` problem, I believe. Some posts about this https://stackoverflow.com/questions/538551/handling-very-large-numbers-in-python – Daniel Hao Oct 25 '21 at 11:06
  • You are right. But the complexity will be quite messy I think. @DanielHao – Fish_n_Chips Oct 25 '21 at 12:40
  • Why is that? ~ `...complexity will be quite messy`? You can still use sliding window tech. to solve it. Right? – Daniel Hao Oct 25 '21 at 13:02
  • yes, but python might have to deal with 100 digit numbers. I don't think it would be a fast solution. Memory is another issue. @DanielHao – Fish_n_Chips Oct 25 '21 at 13:07
  • Ah ... so you imply there is a time requirement or constraint. But your OP did not say that... – Daniel Hao Oct 25 '21 at 13:09
  • Why does it have to be a sliding window algorithm? That's not really a good way to solve this problem. – Matt Timmermans Oct 25 '21 at 17:18
  • You also cannot do `/ a[i - 1]` if `a[i - 1]` is 0. – גלעד ברקן Oct 25 '21 at 18:21
  • Consider user1984's comment - it will certainly help you with the big numbers problem. If you modulo all your numbers first, you will get the same result for k_products_p. You'll also need to be careful of what גלעד ברקן cautions. – Mark Oct 25 '21 at 22:11
  • As mentioned in the question, the elements are all positive integers, so there is no 0 in the array. – Fish_n_Chips Oct 27 '21 at 04:02

1 Answers1

2

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.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87