We are given with two arrays A and B..each of size N...elements of array contains either 1 or 0...
we have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal...
i.e.
a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q]
8 comments:
Array contains only 0's and 1's
Problem is to find the maximum overlapping interval across two arrays. Should be doable using two pointers in linear time.
Isn't the problem same as subtract A from B. Now, you have an array C. Find the subarray with sum zero. (http://inder-gnu.blogspot.com/2010/11/array-contain-ve-and-ve-element-find.html)
i) Is the goal to find the region with 'maximum' sum such that sum_A[p..q] = sum_B[p..q]?
In that case, this may not be an overlap problem.
Let A => 0,0,1,1 and B => 1,1,0,0.
The overlap is 0 but the max_sum is 2 over the region [0..3].
Adding to Pratik's solution, find the largest subarray with sum 0 in C, will give the desired result.
@Pratik
A=[0,1,0,1]
B=[1,1,0,0]
your solution is giving answer from index[1,2] whereas output is from [0,3]!!! correct me if i m wrong!!
A-B is [-1 0 0 1]
Inder's algorithm to compute zero sum subarray should give (0,3) as output. Right?
Time complexity will be o(n^2),even if we use dynamic programming or not.
So, i will go for iterative one.
for(i = 0 to n-1){
sum1 = 0;sum2 = 0;
for( j = i to n-1 ){
sum1+=a[j];
sum2+=b[j];
if(sum1 == sum2){
//store i,j if difference is maximum.
}
}
}
This problem can be solved in Linear time O(n) and O(1) space. Lets see the steps:
Suppose we have 2 arrays a[n] and b[n] with n elements in each.
1. Iterate through each array from 0 to n and count the number of 1's in each. Suppose count1 stores count of 1's in a and count2 stores count of 1's in b.
2. Now we will determine the "end" point of the interval by iterating backwards.
3. Start iterating backwards. Every time a 1 is encountered in a, substract 1 from count1. Every time a 1 is encountered in b, substract 1 from count2.
4. Keep doing this until count1 becomes equal to count2.
5. The point at which count1=count2, we know we have found the end of our interval.
6. Now we need to determine the beginning of our interval, so jump on the start element of both arrays
7. Start iterating towards front on both arrays simultaneously, until a 1 is encountered in either one of them.
8. As soon as we find a 1 in either a or b, we know we have the beginning of the interval.
9. Thus, we have both beginning and end of our intervals.
Time taken: O(n)
Space: O(1)
Nice one by Rochak....:) :) :)
Post a Comment