1
$\begingroup$

I have a sequence of 1s and 0s. For example: $bits = [1, 0, 1, 1, 1, 0]$. I also have an array of positive integers. For example $arr = [12, 23, 4, 6, 8, 0, 24, 72]$. I need to find the index, $i$, in $arr$ of the leftmost element of $bits$ such that

$$\sum_{j = i}^{i + \textrm{length of bits}}{bits[j - i] * arr[j]}$$

is a maximum. Essentially I am maximizing the element-wise multiplication between the two sequences starting at index $i$.

I need to solve it in $O(n\log n)$ or better, but I can only think of a way to do it in $O(n^2)$. I have a feeling prefix sums could be used but am not sure how.

$\endgroup$
3
  • $\begingroup$ You can use FFT to compute all sums in $O(n\log n)$. $\endgroup$ Commented Jun 21, 2020 at 10:10
  • $\begingroup$ Could you ellaborate? @YuvalFilmus $\endgroup$
    – Tom Finet
    Commented Jun 21, 2020 at 14:32
  • $\begingroup$ Try working it out on your own. $\endgroup$ Commented Jun 21, 2020 at 14:58

1 Answer 1

1
$\begingroup$

Let the array consist of the numbers $a_0,\ldots,a_{n-1}$, and let the mask be $b_0,\ldots,b_{k-1}$. Define $$ A = \sum_i a_i x^i, \quad B = \sum_j b_j x^{k-1-j}. $$ Notice that $$ AB = \sum_{i,j} a_i b_j x^{i+k-1-j}, $$ and so the coefficient of $x^{i+k-1}$ in $AB$ is $$ \sum_{j=i}^{i+k-1} a_j b_{j-i}. $$ Therefore if you can calculate $AB$, you can solve your problem.

You can calculate $AB$ in $O(n\log n)$ using FFT.

$\endgroup$
4
  • $\begingroup$ So the largest coefficient will be the maximum value? $\endgroup$
    – Tom Finet
    Commented Jun 22, 2020 at 9:07
  • $\begingroup$ You are required to find the index $i$ at which the sum reaches its maximum. The index can be recovered from the coefficients of $AB$ in linear time. $\endgroup$ Commented Jun 22, 2020 at 9:36
  • $\begingroup$ I've tried to understand FFT but I can't. Why do we even use polynomials here? Could you show me an example of FFT with two example sequences $A$ and $B$? @YuvalFilmus $\endgroup$
    – Tom Finet
    Commented Jun 23, 2020 at 14:36
  • $\begingroup$ There's no need to understand FFT – all you need to know is that it is an efficient way to multiply two polynomials. As for why polynomials come in, I think the answer speaks for itself in that regard. $\endgroup$ Commented Jun 23, 2020 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.