Longest span with same sum in two binary arrays

Given two binary arrays, array1 and array2 with same size. This function will print the longest span with the same sum in two arrays. This can be clearly explained in below example

Example

INPUT:
arr1[] = {0, 1, 0, 1}
arr2[] = {1, 0, 0, 0}
OUTPUT:
3
In the above example, from index 0 to 3 the sum of the elements from index 0 to 3 in the two arrays is same.

Time Complexity: O()

In this method we compute all the subarray sums and check whether they are equal or not. if equal we will take the length of that subarray and compare with maximum subarray length. If it is greater then update.

Algorithm

1. Simply run two loops

2. In the outer loop select an element till end of the array. ie, i=0 to n-1, where n is the size

3. In the inner loop select an element from i to n-1. ie, j=i to n-1

4. find the subarray sums of the two arrays ie, sum1 = sum1 + arr[j] and sum2 = sum2 + arr[j]

5. if the sum's are equal then check whether the length is greater than the previous subarray length and update.

C++ Program

#include <bits/stdc++.h>
using namespace std;

int longestSpan(int arr1[], int arr2[], int n) 
{	
	int length =0, maxlength = 0;//to find the maximum length which has same sum
	for (int i = 0; i < n; ++i)
	{
		int sum1 = 0, sum2 = 0; //sum1, sum2 to keep track of sums of subarrays of arr1 and arr2
		for (int j = i; j < n; ++j)
		{
			sum1 = sum1 + arr1[j];
			sum2 = sum2 + arr2[j];
			if(sum1 == sum2)
			{
				length = j-i+1;
				if(length>maxlength)
				{
					maxlength = length;
				}
			}
		}
	}
	return maxlength; //returns the maximum length

}
int main()
{
	int arr1[] = {0, 1, 0, 1, 1};
	int arr2[] = {1, 0, 0, 1, 0};					
	int n = sizeof(arr1)/sizeof(arr1[0]);
	cout<<"The longest span with same sum in two binary arrays is "<<longestSpan(arr1, arr2,n);
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top