I wonder if it can be solved in less than O(n^2)

Revision en2, by M1v1savva, 2020-11-23 09:29:21

The problem is the following:

We have array $$$a$$$ of $$$n$$$ integers and for each integer $$$k$$$ from $$$1$$$ to $$$n$$$ we want to calculate the number of pairs $$$(i, j)$$$ such that $$$a_i + a_j = k$$$.

I wonder if it can be solved in less than $$$\mathcal{O}(n^2)$$$

UPD: turns out it is a classical FFT problem

Tags #problem discussion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English M1v1savva 2020-11-23 09:29:21 48 Tiny change: 'l{O}(n^2)$' -> 'l{O}(n^2)$\n\nUPD: turns out it is a classical FFT problem'
en1 English M1v1savva 2020-11-23 06:48:59 296 Initial revision (published)