CareerCup

This is same as finding the longest subarray with sum zero in the array C[i] = A[i] - B[i].

Prefix sums + hashtable should give it.

Use 2 cumulative arrays C1 and C2 for both the arrays. The locations C1[i] and C2[i] hold the sum of all values up to index i from both of the arrays respectively.

0. Start with a window of size n(starting at index i=0 and ending at index j=n-1)
1. Compare the values of that window size using arrays C1 and C2. Return (i,j) if they are equal
2. Reduce the window size by 1. Now i and j become 0 and n-2 respectively. Compare the values in the cumulative arrays for the ranges: (0,n-2) & (1,n-1)
3. Repeat steps 1 and 2 until the window size is reduced to 1 or a match in the cumulative arrays is found in which case the corresponding (i,j) would be returned.

**Removed solution as invalid

Here is the C# solution.
Please suggest on optimization, with data structure in case of DP.

void Main()
{
//	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.
	Tuple<int,int> result = FindMaxSubArray(0);
	Console.WriteLine("start index " + result.Item1.ToString() + "end index" + result.Item2.ToString());
}

// Define other methods and classes here
BitArray A = new BitArray(new bool[]{false,true,false,false,true,true,false,false,false,true});
BitArray B = new BitArray(new bool[]{true,true,false,false,false,true,false,false,true,true});
Tuple<int,int> FindMaxSubArray(int startIndex)
{
	int endIndex = 0;
	int additionOfA = 0, additionOfB = 0;
	if(startIndex >= A.Length - 1)
	{
		return new Tuple<int,int>(startIndex,-1000);
	}
	
	for(int i=startIndex; i<A.Length; i++)
	{
		additionOfA = additionOfA + Convert.ToInt32(A[i]);
		additionOfB = additionOfB + Convert.ToInt32(B[i]);
		
		if(additionOfA == additionOfB)
		{
			endIndex = i;
		}
	}
	
	Tuple<int,int> subProblemSolution = FindMaxSubArray(startIndex + 1);
	if((subProblemSolution.Item2 - subProblemSolution.Item1) > (endIndex - startIndex))
	{
		return subProblemSolution;
	}
	else
	{
		return new Tuple<int,int>(startIndex,endIndex);
	}
}

Optimal solution for this is O(N)...
Basically we can try to classify problems such that kind of approach and complexity can be identified quickly first. Anyone wana share their ideas on the usual approaches you follow while problem solving ?

Here is a C# code that refers to a solution mentioned above. Its worst case time complexity is O(n^2) though. I am wondering if there is an O(n) solution.

public static int[] GetLongestBinarySubArrayWithEqualSum(bool[] A, bool[] B)
        {
            int[] SumA = CreateSumArray(A);
            int[] SumB = CreateSumArray(B);

            for (int size = A.Length; size >= 1; size--)
            {
                int count = A.Length - size + 1;
                for (int i = 0; i < count; i++)
                {
                    int j = size - 1 + i;
                    if (HaveEqualSum(SumA, SumB, i, j))
                    {
                        return new int[] { i, j };
                    }
                }
            }

            return null;
        }

        private static bool HaveEqualSum(int[] SumA, int[] SumB, int i, int j)
        {
            return ((SumA[j] - SumA[i]) == (SumB[j] - SumB[i]));
        }

        private static int[] CreateSumArray(bool[] array)
        {
            int[] sumArray = new int[array.Length];
            sumArray[0] = (array[0] ? 1 : 0);
            for (int x = 1; x < array.Length; x++)
            {
                sumArray[x] = sumArray[x - 1] + (array[x] ? 1 : 0);
            }

            return sumArray;
        }

////////
void Func(int a[], int n, int m, int& resi, int& resj)
{
int cnt =0, rcnt=0;
int idx=-1, ridx=-1;
int idx1=-1, ridx1=-1;
printf("cnt1x=%d\n", m);
for(int i=0, j=n-1; i<n && j>=0; i++,j--)
{
if(a[i]) cnt++;
if(a[j])rcnt++;
if(cnt==1 && idx==-1)idx=i;
if(rcnt==1 && ridx==-1)ridx=j;
if(cnt==m && idx1==-1)idx1=i;
if(rcnt==m && ridx1==-1)ridx1=j;
if(cnt==m && rcnt==m)break;

}

int i,j,ri,rj;
if(idx>(n-1-idx1))
{
i=0; j=idx-1;
}
else{
i=idx1+1; j=n-1;
}

if(ridx1>(n-1-ridx))
{
ri=0; rj=ridx1-1;
}
else{
ri=ridx+1; rj=n-1;
}
printf("i,j = %d,%d ri,rj=%d,%d\n", i,j,ri,rj);
if((rj-ri)>(j-i))
{
resi=ri;
resj=rj;
}
else
{
resi=i;
resj=j;
}
}

int main()
{

int a[]={1,0,1,1,1,1,0,1};
int b[]={1,0,0,0,1,1,1,0};
int N=8;

for(int i=0;i<N;i++)
printf("%d ", a[i]);
printf("\nsize=%d\n", N);
for(int i=0;i<N;i++)
printf("%d ", b[i]);
printf("\n");
printf("\n");

int cnt1a=0, cnt1b=0, cnt1x=0;
for(int i=0; i<N; i++)
{
if(a[i])cnt1a++;
if(b[i])cnt1b++;
//if(a[i]!=b[i])
int temp=a[i];
a[i]=((a[i]==b[i]?0:1) && a[i]);
b[i]=((temp==b[i]?0:1) && b[i]);

}
for(int i=0;i<N;i++)
printf("%d ", a[i]);
printf("\nsize=%d\n", N);
for(int i=0;i<N;i++)
printf("%d ", b[i]);
printf("\n");
printf("cnt1xa=%d cnt1xb=%d\n", cnt1a, cnt1b);
cnt1x = cnt1a-cnt1b;

int resi=0, resj=N-1;
if(cnt1x==0) printf("i=0, j=%d\n", N-1);
else if(cnt1x>0)
Func(a, N, cnt1x, resi, resj);
else
Func(b, N, -cnt1x, resi, resj);
printf("resi=%d resj=%d\n", resi, resj);

return 1;
}
\\\\\

void  Func(int a[], int n, int m, int& resi, int& resj)
{
      int cnt =0, rcnt=0;
      int idx=-1, ridx=-1;
      int idx1=-1, ridx1=-1;
      printf("cnt1x=%d\n", m);
      for(int i=0, j=n-1; i<n && j>=0; i++,j--)
      {
              if(a[i]) cnt++;
              if(a[j])rcnt++;
              if(cnt==1 && idx==-1)idx=i;
              if(rcnt==1 && ridx==-1)ridx=j;
              if(cnt==m && idx1==-1)idx1=i;
              if(rcnt==m && ridx1==-1)ridx1=j;              
              if(cnt==m && rcnt==m)break;
              
      }

int i,j,ri,rj;
      if(idx>(n-1-idx1))
      {
       i=0; j=idx-1;
      }
      else{
           i=idx1+1; j=n-1;
           }
      
      if(ridx1>(n-1-ridx))
      {
       ri=0; rj=ridx1-1;
      }
      else{
           ri=ridx+1; rj=n-1;
           }
           printf("i,j = %d,%d  ri,rj=%d,%d\n", i,j,ri,rj);
           if((rj-ri)>(j-i))
           {
                            resi=ri;
                            resj=rj;
           }
           else
           {
                            resi=i;
                            resj=j;            
            }
}

int main()
{

	int a[]={1,0,1,1,1,1,0,1};
	int b[]={1,0,0,0,1,1,1,0};
	int N=8;

	for(int i=0;i<N;i++)
		printf("%d ", a[i]);
		printf("\nsize=%d\n", N);
	for(int i=0;i<N;i++)
		printf("%d ", b[i]);
		printf("\n");
		printf("\n");
		
		int cnt1a=0, cnt1b=0, cnt1x=0;
  for(int i=0; i<N; i++)
  {
          if(a[i])cnt1a++;
          if(b[i])cnt1b++;
          //if(a[i]!=b[i])
          int temp=a[i];
          a[i]=((a[i]==b[i]?0:1) && a[i]);
          b[i]=((temp==b[i]?0:1) && b[i]);
          
  }
for(int i=0;i<N;i++)
		printf("%d ", a[i]);
		printf("\nsize=%d\n", N);
	for(int i=0;i<N;i++)
		printf("%d ", b[i]);
		printf("\n");
		printf("cnt1xa=%d cnt1xb=%d\n", cnt1a, cnt1b);
  cnt1x = cnt1a-cnt1b;
  
  int resi=0, resj=N-1;
  if(cnt1x==0) printf("i=0, j=%d\n", N-1);
  else if(cnt1x>0)
       Func(a, N, cnt1x, resi, resj);
  else 
       Func(b, N, -cnt1x, resi, resj);
  printf("resi=%d resj=%d\n", resi, resj);
  
int abc;
cin>>abc;
	return 1;
}

Sum Of A[i..j] = Sum Of B[i..j] 
Sum Of A[i..j]- Sum Of B[i..j] =0
evaluate (Ai-Bi)..(Aj-Bj) and store for further Cumulative sum (say CSi)
Store CSi in Map, ( let it be like 10, 9,...... , 9, 11) what does it mean is: Span (i to j) contains same set of shuffled data, so subtracting within that span it disappeared and came to a value just before starting of the Span.   
Reference:  shyJohnnie's comment in this discussion
 -- At first it sounds like DP or LCS or suffix, prefix or both of them but finally a math puzzle
 -- I hate to fry brain, I don't know this company's pay structure or is it worth frying ?

Use cumulative array for comparing...

int maxCommonArray(int A[], int B[], int n)
    {
        unordered_map<int, vector<int>> dist;
        int ASum = 0, BSum = 0, ABDiff;
        for (int i=0; i<n; i++)
        {
            ASum = ASum+A[i];
            BSum = BSum+B[i];
            ABDiff = ASum-BSum;
            dist[ABDiff].push_back(i);
        }
        
        //Get the max length;
        int maxLength = -1;
        unordered_map<int, vector<int>>::iterator dI;
        for (dI = dist.begin(); dI != dist.end(); dI++)
        {
            vector<int> crt = dI->second;
            int sizeC = crt.size();
            int crtLen = crt[sizeC-1] - crt[0];
            if (crtLen>maxLength)
                maxLength = crtLen;
        }
        
        return maxLength;
    }

How about this? The below piece of code has the input Arrays 'a' and 'b'.

static void Main(string[] args)
        {
            int x = 0;
            int y = 0;
            int[] a = { 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1};
            int[] b = { 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1};
            int sum_of_Array_A = 0;
            int sum_of_Array_B = 0;
            int n = 0;
            int i = 0;
            int j = 0;
            n = a.Length;
            for (x = 0; x < n; x++)
            {
                for (y = x; y < n; y++)
                {
                    sum_of_Array_A = sum_of_Array_A + a[y];
                    sum_of_Array_B = sum_of_Array_B + b[y];
                    if (sum_of_Array_A == sum_of_Array_B)
                    {
                        if (y - x > j - i)
                        {
                            i = x;
                            j = y;
                        }
                    }
                }
                sum_of_Array_A = 0;
                sum_of_Array_B = 0;
            }
            Console.WriteLine("The maximum length of the sub-array is {0} and the indices are {1}, {2}", j - i, i, j);
        }

C[i] = A[i] - B[i] works simply because:
a_i + ... + a_j = s = b_i + ... + b_j
c_i + ... + c_j = (a_i - b_i) + ... + (a_j - b_j)
= s - s = 0

very simple code and O(n) complexity. hope i didn't miss any corner stone.

int main(){
	int a[] ={1,0,1,0,0,1,1,0,1,0};
	int b[] ={0,1,0,1,1,1,0,0,0,0};
	static int c;
	for(int i=0; i<(sizeof(a)/sizeof(a[0])-1); i++){
		a[i+1] = a[i] + a[i+1];
		b[i+1] = b[i] + b[i+1];
		if (a[i+1] == b[i+1])
			c=i+1;
		}
	cout<<"answer is i =  0 and j =  "<<c<<endl;
	system("pause");
}

void printMaxCommonSubArray(const vector<int> &A, const vector<int> &B)
	{
		assert(A.size() != B.size());
		vector<int> C(A.size(), 0);
		for(int i=0; i<A.size(); ++i)
			C[i] = A[i]-B[i];
		unordered_map<int, int> h;
		int sum = 0;
		h[0] = -1;
		int x = 0;
		int y = 0;
		for(int i=0; i<C.size(); ++i)
		{
			sum += C[i];
			if(h.find(sum) != h.end())
			{
				if(y-x+1 < i- h[sum])
				{
					x = h[sum]+1;
					y = i;
				}
			}
			else
				h[sum] = i;
		}
	}

	cout<<"from\t"<<x << "to\t"<<y<<"\n";

void Max_IJ(int A[], int B[], int len){
Hash SumTbl;
int i,j,indx, max, sum, prev;

i=j=max=sum=0;
for (indx=0; indx<len;indx++){
// sum so far. "-" means B has more 1's than A, and vice versa.
sum += A[indx]-B[indx];
// if the same "sum" is found before then
// it means that A and B has the same # of 1's and 0's from this last "sum"
// up until now. So, the goal here is just to find which time has the max
// indx - prev where prev is the index right after the last time the same
// "sum" is found.
if ((prev=SumTbl.get(sum)) == 0)
SumTbl.put(sum, indx);
else {
if ((indx-(prev+1)) > max) {
max = indx - (prev+1);
i = prev+1;
j = indx;
}
}//else
}//for

cout <<"Max (i,j) at: ("<<i<<","<<j<<")<<endl;

return;
}

// Just re-format the code for better reading from my last post.
// We just need 1 pass over both array at the same time  -- O(n)

void Max_IJ(int A[], int B[], int len){
     Hash SumTbl;
     int i,j,indx, max, sum, prev;

     i=j=max=sum=0;
     for (indx=0; indx<len;indx++){

         // sum so far. "-" means B has more 1's than A, and vice versa.
         sum += A[indx]-B[indx];

        // if the same "sum" is found before then
        // it means that A and B has the same # of 1's and 0's from this last "sum"
        // up until now. So, the goal is just to find which time has the max
        // (indx - (prev+1)) where prev is the index right after the last time the
        // same  "sum" is found.

       if ((prev=SumTbl.get(sum)) == 0)
           SumTbl.put(sum, indx);
       else {
          if ((indx-(prev+1)) > max) {
               max = indx - (prev+1);
               i = prev+1;
              j = indx;
          }
      }//else
  }//for

  cout <<"Max (i,j) at: ("<<i<<","<<j<<")<<endl;

  return;
}