Given two Boolean arrays X and Y, find the length of longest continuous sequence that starts and ends at same index in both arrays and have same sum. In other words, find max(j-i+1) for every j >= i where sum of sub-array X[i, j] is equal to sum of sub-array Y[i, j].

X: {0, 0, 1, 1, 1, 1}

Y: {0, 1, 1, 0, 1, 0}

The length of longest continuous sequence with same sum is 5 as

X[0, 4]: {0, 0, 1, 1, 1} (sum = 3)

Y[0, 4]: {0, 1, 1, 0, 1} (sum = 3)

Naive solution would be to consider every sub-array [i, j] where (j > i) and check if sum of X[i, j] is equal to sum of Y[i, j] or not. If sum is found to be equal and length of the sub-array is more than maximum found so far, we update the result. The time complexity of above solution is O(n^{2}) assuming that sum of each sub-array is computed in constant time.

We can solve this problem in linear time. The idea is to traverse the array and maintain sum of elements of X[] and Y[] till current index and calculate difference between the two sums.

- If the difference is seen for the first time, then we store the difference and current index in a map.

- If difference is seen before and index of previous occurrence is i, then we have found sub-arrays X[i+1, j] and Y[i+1, j] ending at current index j, whose sum of elements is equal. If length of the sub-array is more than maximum found so far, we update the result.

**How does this works?**

Claim: If difference is seen before and index of previous occurrence is i,

then X[i+1, j] = Y[i+1, j]

We can write previous difference di = X[0, i] – Y[0, i]

Similarly, current difference dj = X[0, j] – Y[0, j] or

dj = (X[0, i] + X[i+1, j]) – (Y[0, i] + Y[i+1, j])

If difference is seen before i.e. (dj = di), then

(X[0, i] + X[i+1, j]) – (Y[0, i] + Y[i+1, j]) = X[0, i] – Y[0, i]

X[i+1, j] – Y[i+1, j] = 0 or

X[i+1, j] == Y[i+1, j]

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<bits/stdc++.h> using namespace std; // Given two Boolean arrays X and Y, find the length of longest // continuous sequence that starts and ends at same index in both // arrays and have same sum int findMaxSubarrayLength(bool X[], bool Y[], int n) { // create an empty map unordered_map<int, int> map; // to handle the case when required sequence starts from index 0 map[0] = -1; // stores length of longest continuous sequence int res = 0; // sum_x, sum_y stores sum of elements of X[] and Y[] respectively // till current index int sum_x = 0, sum_y = 0; // traverse both lists simultaneously for (int i = 0; i < n; i++) { // update sum_x and sum_y sum_x += X[i]; sum_y += Y[i]; // calculate difference between sum of elements in two lists int diff = sum_x - sum_y; // if difference is seen for the first time, then store the // difference and current index in a map if (map.find(diff) == map.end()) map[diff] = i; // if difference is seen before, then update the result else res = max(res, i - map[diff]); } return res; } // main function int main() { bool X[] = {0, 0, 1, 1, 1, 1}; bool Y[] = {0, 1, 1, 0, 1, 0}; int n = sizeof(X)/sizeof(X[0]); cout << "The length of longest continuous sequence with same sum is " << findMaxSubarrayLength(X, Y, n); return 0; } |

**Output: **

The length of longest continuous sequence with same sum is 5

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂