4 Sum II

Moderate

0/80

8 upvotes

Asked in companies

Problem statement

You are given 4 arrays 'ARR1’, 'ARR2’, 'ARR3’, 'ARR4’, each consists of ‘N’ numbers. Your task is to return the number of tuples (i, j, k, l) satisfying the following conditions:

0 <= i,j,k,l < ‘N’
ARR1[i] + ARR2[j] + ARR3[k] + ARR4[l] = 0.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N,’ denoting the number of elements in each array.

The next 4 lines of each test case have ‘N’ integers corresponding to the elements of 'ARR1', ‘ARR2’, ‘ARR3’, ‘ARR4’ respectively.

Output Format:

For each test case, return a single integer corresponding to the number of possible tuples.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 500
-100 <= 'ARR1'[i] , ARR2[i], ARR3[i] ,ARR4[i]  <= 100

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

8
1

Explanation of sample input 1:

For the first test case, the possible tuples are:
(0,0,0,0) :  ‘ARR1[0]’ +  ‘ARR2[0]’ +  ‘ARR3[0]’ +  ‘ARR4[0]’ = 0.
(0,0,1,1) :  ‘ARR1[0]’ +  ‘ARR2[0]’ +  ‘ARR3[1]’ +  ‘ARR4[1]’ = 0.
(0,1,0,0) :  ‘ARR1[0]’ +  ‘ARR2[1]’ +  ‘ARR3[0]’ +  ‘ARR4[0]’ = 0.
(0,1,1,1) :  ‘ARR1[0]’ +  ‘ARR2[1]’ +  ‘ARR3[1]’ +  ‘ARR4[1]’ = 0.
(1,0,0,0) :  ‘ARR1[1]’ +  ‘ARR2[0]’ +  ‘ARR3[0]’ +  ‘ARR4[0]’ = 0.
(1,0,1,1) :  ‘ARR1[1]’ +  ‘ARR2[0]’ +  ‘ARR3[1]’ +  ‘ARR4[1]’ = 0.
(1,1,0,0) :  ‘ARR1[1]’ +  ‘ARR2[1]’ +  ‘ARR3[0]’ +  ‘ARR4[0]’ = 0.
(1,1,1,1) :  ‘ARR1[1]’ +  ‘ARR2[1]’ +  ‘ARR3[1]’ +  ‘ARR4[1]’ = 0.

Hence,  the answer is 8.

For the second test case,the possible tuples are:
(0,0,0,0) : ‘ARR1[0]’ +  ‘ARR2[0]’ +  ‘ARR3[0]’ +  ‘ARR4[0]’ = 0.

Hence, the answer is 1.

Sample Input 2:

Sample Output 2:

3
0

Hint 1

Hint 2

Hint 3

Can you try each possible tuple?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

In this approach, we will iterate over all possible tuples and check if the sum of 4 numbers is 0 or not. If they sum up, we will increment ‘AND'. Return the number of tuples in the end.

Algorithm:

We will declare a variable ‘ANS’ to store the number of tuples that satisfies the given condition.
For each index ‘i’ in the range from 0 to n-1, do the following:
- For each index ‘j’ in the range from 0 to n-1, do the following:
  - For each index ‘k’ in the range from 0 to n-1, do the following:
    - For each index ‘l’ in the range from 0 to n-1, do the following:
      - If sum of ‘ARR1[i]’ + ‘ARR2[j]’ + ‘ARR[k]’ + ‘ARR[l]’ is equal to 0:
        Set ‘ANS’ as ‘ANS’ + 1.
Return ‘ANS’.

Time Complexity

O(N^4), where ‘N’ is the number of elements in 'ARR'.

In this approach, we are iterating over all the tuples and the total numbers of tuples are N^4. Hence the overall time complexity is O(N^4).

Space Complexity

O(1).

We are using only constant space. Hence the overall space complexity is O(1).

(100% EXP penalty)

4 Sum II

Console