Count quadruplets with a zero sum

Given four integer arrays, count the number of quadruplets with a zero sum, including exactly one element from each array.

For example,

Input:

A = [0, -1, 1]
B = [-1]
C = [2, 4]
D = [-4, 0]

Output: 2

Explanation: There are two quadruplets with a zero sum, as follows:

A[1] + B[0] + C[0] + D[1] = [-1 + -1 + 2 + 0]
A[2] + B[0] + C[1] + D[0] = [ 1 + -1 + 4 + -4]

The problem of finding the quadruplet A[i] + B[j] + C[k] + D[l] = 0 can be broken down into finding the pair (A[i] + B[j]) that equals -(C[k] + D[l]). The idea is to loop through the elements of the first two arrays. For each pair, calculate their sum and keep track of sum-count mappings in a hash table. Next, calculate the sum of each pair in the other two arrays. If the opposite sum exists in the hash table, we have found a quadruplet.

The algorithm can be implemented as follows in C++, Java, and Python:

C++

#include <iostream>

#include <vector>

#include <unordered_map>

using namespace std;

int find4Tuples(vector<int> const &A, vector<int> const &B,

vector<int> const &C, vector<int> const &D)

{

// create a map to store pair sum-frequency mappings

unordered_map<int, int> map;

// consider each pair of the first two arrays

for (int i : A)

{

for (int j : B)

{

// calculate the sum of each pair and update its count in the map

int sum = i + j;

map[sum] += 1;

}

// store the count of quadruplets with a zero sum

int count = 0;

// consider each pair of the remaining two arrays

for (int i : C)

{

for (int j : D)

{

// calculate the sum of each pair

int sum = i + j;

// increment the quadruplet count, if the opposite sum exists in the map

count += map[-sum];

}

return count;

}

int main()

{

vector<int> A = { 0, -1, 1 } ;

vector<int> B = { -1 };

vector<int> C = { 2, 4 };

vector<int> D = { -4, 0 };

cout << find4Tuples(A, B, C, D) << endl;

return 0;

}

Download Run Code

Output:

2

Java

import java.util.HashMap;

import java.util.Map;

class Main

{

public static int find4Tuples(int[] A, int[] B, int[] C, int[] D)

{

// create a map to store pair sum-frequency mappings

Map<Integer, Integer> map = new HashMap<>();

// consider each pair of the first two arrays

for (int i : A)

{

for (int j : B)

{

// calculate the sum of each pair and update its count in the map

int sum = i + j;

map.put(sum, map.getOrDefault(sum, 0) + 1);

}

// store the count of quadruplets with a zero sum

int count = 0;

// consider each pair of the remaining two arrays

for (int i : C)

{

for (int j : D)

{

// calculate the sum of each pair

int sum = i + j;

// increment the quadruplet count, if the opposite sum exists in the map

count += map.getOrDefault(-sum, 0);

}

return count;

}

public static void main(String[] args)

{

int[] A = { 0, -1, 1 } ;

int[] B = { -1 };

int[] C = { 2, 4 };

int[] D = { -4, 0 };

System.out.println(find4Tuples(A, B, C, D));

}

Download Run Code

Output:

2

Python

def find4Tuples(A, B, C, D):

# create a dictionary to store pair sum-frequency mappings

dict = {}

# consider each pair of the first two arrays

for i in A:

for j in B:

# calculate the sum of each pair and update its count in the dictionary

sum = i + j

dict[sum] = dict.setdefault(sum, 0) + 1

# store the count of quadruplets with a zero sum

count = 0

# consider each pair of the remaining two arrays

for i in C:

for j in D:

# calculate the sum of each pair and increment the quadruplet count if

# the opposite sum exists in the dictionary

sum = i + j

count += dict.setdefault(-sum, 0)

return count

if __name__ == '__main__':

A = [0, -1, 1]

B = [-1]

C = [2, 4]

D = [-4, 0]

print(find4Tuples(A, B, C, D))

Download Run Code

Output:

2

The time complexity of the above solution is O(n²) and requires O(n²) extra space, where n is the size of the input.

Count quadruplets with a zero sum

C++

Java

Python

Share this: