CareerCup

#include <iostream>
using namespace std;

int main()
{
    int a[] = {0,0,1,1,0,1};
    int b[] = {1,0,1,0,0,0};

    int n = sizeof(a)/ sizeof(a[0]);
    int p = 0, q = 0, sumA = 0, sumB = 0, sum = 0;

    for(int k = 0; k < n-1; k++)
    {
     for (int j = n-1; j > 0; j--)
       {
           sumA = 0; sumB = 0;
    
        for(int i = k; i <= j; i++)
         { 
           sumA += a[i];
           sumB += b[i];
           }
        if(sumA == sumB && j > k && (q-p) < (j-k))
         {
           p = k; q = j; sum = sumA;
           }
        }
 }

 cout << p << " " << " "  << q << "  " << sum << endl;
    
 return 0;
 }

can be done in O(n*n) comfortably
But interview is definately looking for better than O(n*n)

Solution is O(N). It is the Longest Common Substring with a modification. So only one loop

There are n*(n+1)/2 intervals that can be formed using various combinations of p and q for a single array. Which means there are n*(n+1)/2 elements. Now the question is,
if K = n*(n+1)/2 can you design an algorithm that will find the max from K in less than K comparisons. Does that make sense? finding a max of an array of size K in sublinear time. How? I dont see a solution.
The best solution I can see is O(n+2+3+4+..(n-1)) => O(n*(n+1)/2) = O(n^2)

Solution:
Since, all the values are binary, all we need is count the number of bits set. So.
Count all the bits set in both arrays, totalSumA, totalSumB
when p - q == n-1, we do 1 comparison (totalSumA==totalSumB) ??
when p - q == n-2, we do 2 comparisons //just subtract the ends from totalSumA and totalSumB and compare
when p - q == n-i , we do i comparisons
=> total number of comparisons required = n*(n+1)/2
=> O(n^2)

form a new array sub = a - b. Now the problem transcends to finding the sub array in this array sub (which has both positive and negative numbers) with zero sum. This can be done in O(n) time.

"finding the sub array in this array sub (which has both positive and negative numbers) with zero sum. This can be done in O(n) time."

is there a way 2 do dis in O(n) other than using hashing/mapping??

Hi Guys how about this aproach

A = {0,0,0,1,1,0,1}

B = {0,1,0,1,0,0,0}

sum_a = {0,0,0,1,2,2,3} // i.e a[i] = a[i] + a[i - 1]
sum_b = {0,1,1,2,2,2,2}

now begin from the back of sum_a and sum_b 

if(sum_a[a_size] == sum_b[b_size])
{
   while(sum_a[a_size] == sum_b[b_size]){
    a_size --;
    b_size --;
   }
   return a_size; // from this index to 0 is the sequence we are looking for 
}
if(sum_a[a_size] > sum_b[b_size])
{
      b_size--;
}
if(sum_a[a_size] < sum_b[b_size])
{
        a_size--;
}
if( a_size == 0 || b_size == 0  )
return -1 ; // no such sequence exists

//I hope i am able explain logic clearly here , if any doubts let me know

Nice solution...But, don't you feel any need for an outer loop ??

bt its nt alws necessary dat one of d index is 0..

Another solution ....

make an array c such that c[i]=b[i]-a[i]
Now the problem reduces to finding the maximum subarray such that sum of that subarray is zero.
This problem has been discussed before.
And is applicable for any numbers not only for 1 and 0's

Another solution ....

make an array c such that c[i]=b[i]-a[i]
Now the problem reduces to finding the maximum subarray such that sum of that subarray is zero.
This problem has been discussed before.
And is applicable for any numbers not only for 1 and 0's

@rya

question id is 4682948

do it like this:
firstly, for each position in array a and b, record how many 1s before it.
1 0 1 0 1 0 => 0 1 1 2 2 3 3
0 1 1 1 0 1 => 0 0 1 2 3 3 4
then subtract the r_a(top one) from the r_b(bot one)
0 -1 0 0 -1 0 1
then your problem become to find the longest interval between two identical numbers. for example, here, it is 0: the first 0 appears at position 0 and the last 0 appears at 5. the interval between 0s is 5. no other numbers can make a longer interval than this.
to solve this problem: build two array s and q with size 2*n, n is the size of a or b;
for (int i = 0; i <= n; ++i)
{

s[diff[i]+n] = i;

}
so finally s records the first appearance position of each value (from -n to n);
then do it in an opposite way, ie i from n to 0
q records the last appearance of a value.
q[i] - s[i] is the longest interval of each value;
choose the largest one, output q[i] and s[i]-1;
done

time complexity 0(2n), space O(2n);

I think it can be done in O(n) as follows.

take the bitwise and of both arrays A and B and store it in an array called Res[].The indices of first and last set bits of array Res[] will be the desired interval.


Please let me know in case if i am missing some thing.
Thanks.