Last Updated: 30 Aug, 2021
4 Sum II
Moderate
Asked in companies
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.
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
Approaches
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.
- If sum of ‘ARR1[i]’ + ‘ARR2[j]’ + ‘ARR[k]’ + ‘ARR[l]’ is equal to 0:
- For each index ‘l’ 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 ‘j’ in the range from 0 to n-1, do the following:
- Return ‘ANS’.
In this approach, First we will sort ARR4 so that we can apply binary search on that.We will try to form each possible triplet among the elements of ‘ARR1’ ’ARR2’ and ‘ARR3’. We will store the sum of these triplets in a variable ‘SUM’. Now using binary search we will try to find the number of occurrences of -1*’SUM’ using function count(‘ARR4’,’REQ’).We will update ‘ANS’ as ‘ANS’ + count(‘ARR4’,-1*’SUM’).
count(‘ARR’, ‘REQ’) will return the number of occurrences of ‘REQ’ in array ‘ARR’ using binary search.
Algorithm:
- Declaring count(‘ARR’, ‘REQ’). This function will return the number of occurrences of ‘REQ’ in ‘ARR’.
- Set ‘FIRST’ as -1. (Index of the first occurrence of ‘REQ’ in ‘ARR’).
- Set ‘L’ as 0.
- Set ‘R’ as N-1.
- While ‘L’ <= ‘R’, do the following:
- Set ‘MID’ as (L+R)/2.
- If ARR[‘MID’] is equal to REQ:
- Set ‘FIRST’ as MID.
- If ARR[‘MID’] <= REQ:
- Set ‘R’ as ‘MID’-1.
- Else:
- Set ‘L’ as ‘MID’ + 1.
- If ‘FIRST’ is equal to -1 means ‘ARR’ does not consist of any occurrences of ‘REQ’, hence return 0.
- Set ‘LAST’ as -1. (Index of the last occurrence of ‘REQ’ in ’ARR’ ).
- Set ‘L’ as 0.
- Set ‘R’ as N-1.
- While ‘L’ <= ‘R’, do the following:
- Set ‘MID’ as (L+R)/2.
- If ARR[‘MID’] is equal to REQ:
- Set ‘LAST’ as MID.
- If ARR[‘MID’] < REQ:
- Set ‘R’ as ‘MID’-1.
- Else:
- Set ‘L’ as ‘MID’ + 1.
- Return ‘LAST’-’FIRST’+1.(No of occurrences of ‘REQ’ in ‘ARR’).
- Declare a variable ‘ANS’ to store the number of tuples that satisfy the given condition.
- Sort the array ‘ARR4’.
- 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:
- Set ‘REQ’ as -1*(‘ARR1[i]’ + ‘ARR2[j]’ + ‘ARR3[k]’).
- Set ANS as ANS + count(‘REQ’, ‘ARR4’).
- For each index ‘k’ 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:
- Return ‘ANS’.
In this approach, We will declare two hashmaps ‘HASHMAP1’ and ‘HASHMAP2’. ’HASHMAP1’ will store the frequency of the sum of all pairs of elements of ‘ARR1’ and ‘ARR2’.Similarly ’HASHMAP2’ will store the frequency of sum of all pairs of elements of ‘ARR3’ and ‘ARR4’. Now we will iterate through all elements of ‘HASHMAP1’ and search for the required element in ‘HASHMAP2’ and will update the ‘ANS’ accordingly.
Algorithm:
- We will declare a variable ‘ANS’ to store the number of tuples that satisfies the given condition.
- Declare two hashmaps ‘HASHMAP1’ and ‘HASHMAP2’.
- 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:
- Increment the value of HASHMAP1[ ARR1[i] + ARR2[j] ].
- Increment the value of HASHMAP2[ ARR3[i] + ARR4[j] ].
- For each index ‘j’ in the range from 0 to n-1, do the following:
- For each ‘VAL’ in ‘HASHMAP1’, do the following:
- Set ‘REQ’ as -1*VAL.
- Update ANS as ANS + (HASHMAP1[VAL] * HASHMAP2[REQ]).
- Return ‘ANS’.