How can I efficiently find the number of quadruples in an array which sum up to k?
Difference between en1 and en2, changed 109 character(s)
Example : [4,2,2,2,2], k=8↵

Answer : — (1)↵

As only 1 quadruple(2+2+2+2=8) exists whose sum is '8' :-)↵

I know the brute-force O(n^4) algorithm , I even know an O(n^2.log(n)) algorithm , but it unfortunately does not work with duplicate elements :-(↵

Any better-efficient way to solve it ? :-)↵

Constraints:- Length of array can be as long as 10^5 and array can consist of duplicate elements as well.↵

Thanks!:-)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English KaranTheGreat 2019-02-21 14:12:31 109
en1 English KaranTheGreat 2019-02-21 14:00:23 397 Initial revision (published)