CODEWITHSUNDEEP
c++arraysalgorithm
andre
andre

Reputation: 765

Sum of 4 integers in 4 arrays

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

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

Output: 2

Explanation: The two tuples are:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

I just came up with a solution that concatenates all the vectors and find the 4 sum. But I know there is a better solution. Would someone explain a better solution ? I just see codes using O(N^2) but I can't understand it.

Upvotes: 1

Views: 1635

Answers (1)

Kaidul
Kaidul

Reputation: 15885

This was my O(n^2) solution:

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    int n = A.size();
    int result = 0;
    unordered_map<int,int> sumMap1;
    unordered_map<int,int> sumMap2;

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            int sum1 = A[i] + B[j];
            int sum2 = C[i] + D[j];
            sumMap1[sum1]++;
            sumMap2[sum2]++;
        }
    }
    for(auto num1 : sumMap1) {
        int number = num1.first;
        if(sumMap2.find(-1 * number) != sumMap2.end()) {
            result += num1.second * sumMap2[-1 * number];
        }
    }
    return result;
}

The core observation is - if W + X + Y + Z = 0 then W + X = -(Y + Z).

Here I used two hash-tables for each of possible sums in both (A, B) and (C, D) find number of occurrences of this sum.

Then, for each sum(A, B) we can find if sum(C, D) contains complimentary sum which will ensure sum(A, B) + sum(C, D) = 0. Add (the number of occurrences of sum(a, b)) * (number of occurrences of complimentary sum(c,d)) to the result.

Creating sum(A, B) and sum(C, D) will take O(n^2) time. And counting the number of tuples is O(n^2) as there are n^2 sum for each pairs(A-B, C-D). Other operation like insertion and search on hashtable is amortized O(1). So, the overall time complexity is O(n^2).

Upvotes: 2

Related Questions