Longest Span with same Sum in two Binary arrays - GeeksforGeeks

Longest Span with same Sum in two Binary arrays - GeeksforGeeks

Longest Span with same Sum in two Binary arrays

Given two binary arrays arr1[] and arr2[] of same size n. Find length of the longest common span (i, j) where j >= i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] + arr2[i+1] + …. + arr2[j].

Examples:

Input: arr1[] = {0, 1, 0, 0, 0, 0};         arr2[] = {1, 0, 1, 0, 0, 1};  Output: 4  The longest span with same sun is from index 1 to 4.    Input: arr1[] = {0, 1, 0, 1, 1, 1, 1};         arr2[] = {1, 1, 1, 1, 1, 0, 1};  Output: 6  The longest span with same sun is from index 1 to 6.    Input: arr1[] = {0, 0, 0};         arr2[] = {1, 1, 1};  Output: 0    Input: arr1[] = {0, 0, 1, 0};         arr2[] = {1, 1, 1, 1};  Output: 1  

We strongly recommend you to minimize your browser and try this yourself first.

Method 1 (Simple Solution)
One by one by consider same subarrays of both arrays. For all subarrays, compute sums and if sums are same and current length is more than max length, then update max length. Below is C++ implementation of simple approach.

Read full article from Longest Span with same Sum in two Binary arrays - GeeksforGeeks