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

Правка en2, от 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

Теги #problem discussion

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский 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 Английский M1v1savva 2020-11-23 06:48:59 296 Initial revision (published)