CODEWITHSUNDEEP
algorithmsubsequence
Neha K
Neha K

Reputation: 13

Equal sum subsequence in 2 arrays

Given 2 arrays A and B, select a subsequence X from A and Y from B, sum(X) should be equal to sum(Y). We have to find the number of ways in which we can select this type of subsequences.

Number of elements in array can be at most 100 Values in array -100 to 100

My approach: Generate all subsequences of both arrays, take their sum and for each possible sum, multiply the no of subsequence we found in array A with no of subsequence we found in array B having that sum.

This is very inefficient as generating all the subsequences will be of O(2^100)

Can anybody help me with this? I don't need the code, just the idea of algo will be very much helpful.

Upvotes: 1

Views: 1171

Answers (1)

attempt0
attempt0

Reputation: 834

Notice that the range of sum(X) or sum(Y) is from -10000 to 10000
So we can keep track of all the values if they are stored in an array of length 20001
We can loop every element in one of the array and keep track of the sum count array and repeat for the other array.

For each element, we either add the element to the sum or we don't add the element to the sum.

  1. If we add the element, sum count array will shift by the value of the element.
  2. If we don't add the element, sum count array will remain unchanged.
// let the sum count array be named num and has length 20001 (all filled with 0)
vector<int> num(20001, 0);
// the following line set count of sum = 0 to 1 (position 10001(one based) in the array, As I shift all value by 10000 to handle negative sums)
num[10000] = 1;
for (int i = 0; i < 100; ++i) {
    vector<int> num2(num); // copy num to num2 (Done (2.))
    for (int j = 0; j < 20001; ++j) {
        if (j + A[i] >= 0 && j + A[i] < 20001)
            // Add (1.)
            num2[j + A[i]] += num[j];
    }
    // c++ optimization, we just want num to become num2 and we can destroy num2
    num = num2.move(); 
}

If we sum up array from (1.) and (2.), it will be the new sum count array ready for the next element to be inserted. complexity of each element will be O(20001)
Overall complexity would be around O(2 * 20001 * 100) to generate the sum count array.
Additional O(20001) to get the final answer.
So overall complexity is O(2 * 20001 * 100 + 20001)

Upvotes: 2

Related Questions