Longest Continuous Sequence - C++ Solution

1. Introduction

This blog post addresses a unique array comparison problem. Given two binary arrays, the objective is to find the length of the longest continuous sequence that starts and ends at the same index in both arrays and has an equal sum. This problem is a test of efficient array traversal and comparison techniques.

Problem

We are given two binary arrays X and Y. The task is to find the length of the longest continuous sequence such that it starts and ends at the same index in both arrays and the sum of elements in the sequence is the same for both arrays.

2. Solution Steps

1. Compute the difference array, diff, where each element is the difference of corresponding elements in X and Y.

2. Find the longest subarray in diff with a sum of 0.

3. Use a hash map to store the first occurrence of each cumulative sum in the diff array.

4. Traverse the diff array, updating the length of the longest subarray with sum 0.

3. Code Program

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int longestEqualSumSubarray(const vector<int>& X, const vector<int>& Y) {
    int maxLength = 0, sum = 0;
    unordered_map<int, int> sumIndexMap;
    vector<int> diff;

    for (int i = 0; i < X.size(); i++) {
        diff.push_back(X[i] - Y[i]);
    }

    for (int i = 0; i < diff.size(); i++) {
        sum += diff[i];

        if (sum == 0) {
            maxLength = i + 1;
        }

        if (sumIndexMap.find(sum) == sumIndexMap.end()) {
            sumIndexMap[sum] = i;
        } else {
            maxLength = max(maxLength, i - sumIndexMap[sum]);
        }
    }

    return maxLength;
}

int main() {
    vector<int> X = {0, 0, 1, 1, 1, 1};
    vector<int> Y = {0, 1, 1, 0, 1, 0};

    cout << "Longest Continuous Sequence: " << longestEqualSumSubarray(X, Y) << endl;
    return 0;
}

Output:

Longest Continuous Sequence: 5

Explanation:

The function longestEqualSumSubarray calculates the longest continuous sequence in two binary arrays that have the same sum. It first computes a difference array, diff, and then finds the longest subarray in this array with a sum of 0. The hash map sumIndexMap is used to track the first occurrence of each cumulative sum. For the given arrays, the longest sequence where X[i, j] and Y[i, j] have the same sum is 5, as seen in the subarrays X[0, 4] and Y[0, 4].