Post date: Aug 12, 2013 2:14:7 AM
Problem
Given 2 binary arrays A and B i.e. containing only 0s and 1s each of size N.
Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i
(i.e. the length of the set i,j) is the maximum possible value.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i
Created Data : 11-08-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
bool FindIJ(int arr1[], int arr2[], int len, int& low, int& up)
{
vector<int> accSum1;
vector<int> accSum2;
accSum1.push_back(0);
accSum2.push_back(0);
int sum1(0);
int sum2(0);
for(int i = 0; i < len; ++i){
sum1 += arr1[i];
sum2 += arr2[i];
accSum1.push_back(sum1);
accSum2.push_back(sum2);
}
int maxDiff(0);
low = up = 0;
for(int i = 0; i < len; ++i){
for(int j = i; j < len + 1; ++j){
if(accSum1[j] - accSum1[i] == accSum2[j] - accSum2[i]){
if(j - i > maxDiff){
maxDiff = j - i;
low = i;
up = j;
}
}
}
}
up --;
return (low < up);
}
void DoTest(int* arr1, int* arr2, int len)
{
cout << "Array 1" << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << " " << arr1[i];
}
cout << endl << endl;
cout << "Array 2" << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << " " << arr2[i];
}
cout << endl << endl;
int i, j;
if(FindIJ(arr1, arr2, len, i, j)){
cout << "i = " << i << endl;
cout << "j = " << j << endl;
}
else{
cout << "No i and j meet requirement" << endl;
}
cout << "------------" << endl;
}
int main(int argc, char* argv[])
{
int arr1[] = {0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0};
int arr2[] = {1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0};
DoTest(arr1, arr2, 11);
int arr3[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int arr4[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
DoTest(arr3, arr4, 11);
int arr5[] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
int arr6[] = {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1};
DoTest(arr5, arr6, 11);
int arr7[] = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int arr8[] = {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1};
DoTest(arr7, arr8, 11);
int arr9[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
int arr10[] = {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0};
DoTest(arr9, arr10, 11);
return 0;
}
Output
Array 1
0 1 0 0 0 1 0 0 1 0 0
Array 2
1 0 1 1 1 0 1 1 0 1 0
i = 5
j = 8
------------
Array 1
0 0 0 0 0 0 0 0 0 0 0
Array 2
1 1 1 1 1 1 1 1 1 1 1
No i and j meet requirement
------------
Array 1
1 1 1 1 0 0 0 0 0 0 0
Array 2
0 0 0 0 1 1 1 1 1 1 1
i = 0
j = 7
------------
Array 1
1 0 0 0 0 0 0 0 0 0 0
Array 2
0 0 0 0 1 1 1 1 1 1 1
i = 0
j = 4
------------
Array 1
0 0 0 0 0 0 0 0 0 0 1
Array 2
0 0 0 0 1 0 0 0 0 0 0
i = 0
j = 10
------------
Press any key to continue . . .