Quadruplet Sum

faq

1. What are the APPLICATIONS OF QUADRUPLET SUM PROBLEM
This problem is the most basic of a class of algorithms developed by Howgrave-Graham and Joux
A variation of this problem is used in various other problems like convolution
It finds many uses in computational geometry

2. What exactly is a quadruplet sum?
Ans -> Sum of four numbers is equal to target

3. What exactly is quadruplets(a,b,c,d)?
Ans -> (a, b, c, d) is represents array indexes i.e. A1[a] + A2[b] + A3[c] + A4[d]

4. can we use HashMap into this questions?
Ans -> Yes, we can do this question using hashmap approach also. 

5. Why the time complexity is O(n ^ 3)?
ans ->O(n^k−1), or O(n^3)for 4Sum. We have k - 2 loops, and twoSum is O(n).

Note that for k > 2, sorting the array does not change the overall time complexity.

hints

1. If you have already read and implement the 3sum and 4sum by using the sorting approach: reduce them into 2sum at the end, 
2. you might already got the feeling that, all ksum problem can be divided into two problems:
2sum Problem
Reduce K sum problem to K – 1 sum Problem
3. We could use recursive to solve this problem. Time complexity is O(N^(K-1)).

MCQ

A. What exactly is a quadruplet sum?
1. Sum of two numbers is equal to target
2. Sum of three numbers is equal to target
3. Sum of four numbers is equal to target
4. None Of the above

Ans -> 3. Sum of four numbers is equal to target
Exlpain : Sum of four numbers is equal to target is a quadruplet sum.

B. As per the question, (a, b, c, d) is represents?
1. Arrays Elements
2. Arrays Indexes
3. Arrays name
4. None of the above

Ans -> 2. Arrays Indexes
Explain : A1[a]+A2[b]+A3[c]+A4[d] = target

C. what we are stored into our HashMap ?
1. Sum with their Indexes
2. Sum with their occurences
3. Distinct Sum of elements
4. None of the above

Ans -> 2. Sum with their occurences

D. What is the Time Complexity to solve this question?      
1. O(n)
2. O(n ^ 3)
3. O(n ^ 2)
4. O(1)

Ans : 2. O(n ^3)
Explain :O(n^k−1), or O(n^3)for 4Sum. We have k - 2 loops, and twoSum is O(n).

Note that for k > 2, sorting the array does not change the overall time complexity.

E. What is the average space complexity of this problem?
a) O(n*n)
b) O(1)
c) O(n)
d) None of the above
Ans: c
O(n) in worst case for generalised algorithm.