arrays - Is it possible to do 3-sum/4-sum...k-sum better than O(n^2) with these conditions? - Tech Interview -

this classic problem, curious if possible better these conditions.

problem: suppose have sorted array of length 4*n, is, each element repeated 4 times. note n can natural number. also, each element in array subject constraint 0 < a[i] < 190*n. there 4 elements in array such a[i] + a[j] + a[k] + a[m] = v, v can any positive integer; note must use 4 elements , can repeated. not requirement find 4 elements satisfy condition, rather, showing can done given array , v enough.

ex : = [1,1,1,1,4,4,4,4,5,5,5,5,11,11,11,11] v = 22

this true because, 11 + 5 + 5 + 1 = 22.

my attempt:

instead of "4sum" first tried k-sum, proved pretty difficult instead went variation. first solution came rather naive o(n^2). however, given these constraints, imagine can better. tried dynamic programming methods , divide , conquer, didn't quite me anywhere. specific, not sure how cleverly approach in way can "eliminate" portions of array without having explicitly check values against or permutations.

1. make vector s0 of length 256n s0[x]=1 if x appears in a.
2. perform convolution of s0 produce new vector s1 of length 512n. s1[x] nonzero iff x sum of 2 numbers in a.
3. perform convolution of s1 make new vector s2. s2[x] nonzero iff x sum of 4 numbers in a.
4. check s2[v] answer.

convolution can performed in o(n log n) time using fft convolution (http://www.dspguide.com/ch18/2.htm) or similar techniques.

since @ 4 such convolutions performed, total complexity o(n log n)