6.1k views

Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ or report that there is not such span,

1. Takes $O(3^{n})$ and $\Omega(2^{n})$ time if hashing is permitted
2. Takes $O(n^{3})$ and $\Omega(n^{2.5})$ time in the key comparison mode
3. Takes $\Theta (n)$ time and space
4. Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number

edited | 6.1k views
+2

i = -1, j = -1 //keeps track of longest span i = left index and j = right index

Suppose we have an Array indexed as A[1....n] and B[1....n]

x = n/2 +1 , y= n/2+1 //used to span the arrays x = left and y = right

Asum = A[x]; // sum obtained while spanning array A
Bsum = B[y]; // sum obtained while spanning array B
n1=n;
n=1;
while(n<=n1)
{
if(Asum == Bsum)
{
i = x;
j = y;
}
if(n%2==1 && y+1 <= n1)
{
y++;
Asum = Asum + A[y];
Bsum = Bsum + B[y];
}
else if (x-1 >=1)
{
x--;
Asum = Asum + A[x];
Bsum = Bsum + B[x];
}
n++;
}

If i=-1 and j =-1 then no such span

else i,j gives the index values

Takes Θ(n) time for spanning array and Θ(n) space for storing arrays

Answer is $C$.

0
+6

A good video for explanation-  .

Answer is (C). Following algorithm would do.

Since array is binary, the max sum will go until $n$ and so the sum difference of the two arrays can vary between $-n$ and $n$. We use array $start$ to keep the starting index of each possible sum (hence of size $2n+1$) and array $end$ to keep the ending index (these two arrays work like hash tables and since we have only $2n+1$ possible keys, we can do a perfect hashing). So, our required solution will be $max(end[i]-start[i])$ provided both are assigned values.

The algorithm works as follows:

1. Initialize  $diff$  array to contain the difference of sum of elements of array a and b. i.e., $diff[i] = \sum_{i=0}^n a[i] - b[i]$.
2. Now $diff[i]$ can have values from $-n$ to $n$ which gives $2n+1$ possible values and the first occurrence of a $diff$ value marks the beginning of a span and the last occurrence marks the end. We use $start$ and $end$ array for storing these two positions for the $2n+1$ possible values.
3. Now, the largest value of $end[i] - start[i]$ for any $i$, will be the largest span and the start of it will be $start[i] + 1$, and end will be $end[i]$. If the span is starting from first position itself (arrays $a$ and $b$ have same first elements), then it will start from $start[i]$ itself.
#include <stdio.h>

#define size 100 //assume n is less than 100
int main()
{
int n, a[size], b[size];
int start[2*size+1], end[2*size+1];
int sum1 = 0, sum2 = 0, i;
int diff[size];
printf("Enter n: ");
scanf("%d", &n);
for(i = 0; i < n; i++)
{
printf("Enter a[%d]: ", i);
scanf("%d", &a[i]);
}
for(i = 0; i < n; i++)
{
printf("Enter b[%d]: ", i);
scanf("%d", &b[i]);
}

for(i = 0; i < n; i++)
{
if(a[i]) sum1++;
if(b[i]) sum2++;
diff[i] = sum1 - sum2;
}
for(i = 0; i < 2*n; i++)
start[i] = -1,end[i] = -1;
start[n] = end[n] = 0;
//initially sum is 0 at the beginning of array and
//the first n-1 elements of start and end are used
//if sum of A till ith element is less than sum of B till ith element
for(i=0; i < n; i++)
{
if(start[diff[i] + n] == -1)//interested only in the first occurrence of diff[i]
start[diff[i] + n] = i;
end[diff[i] + n] = i;//interested in the last occurrence of diff[i]
}
int max = -1;
int savei = -1; //savei is for storing the sum having the largest span

for(i = 0; i < 2*n; i++)
{
if(start[i] > -1 && (end[i] - start[i] > max))
{
max = end[i] - start[i];
savei = i;
}

}
if(savei >= 0)
{
printf("The largest span is from %d to %d\n", start[savei]+(savei != n), end[savei]);
//when sum zero is having the largest span, span starts from first element itself.
//Else, the span starts from the next element from which the span does not change
}
else
{
printf("No span\n");
}
}

by Veteran (425k points)
edited
0
Yes. You are correct. I wrongly assumed each element in the span to be same as well, which is not needed. The question asks only for sum to be same. You have an algorithm for it?
+1
+1
Can you please briefly explain this algorithm ......?
0
What is being stored in start and end and why is n added every time ? @Arjun sir
+1
is it clear now?
+1
Yes nice logic !!
0
sir i think you should explain the algo in details and then go for the source code ..as we are not getting it clearly
0
0
@Arjun Sir, in the loop where start and end arrays are getting updated, it is storing ending index value in end[] array which is not in continuation with previous values.

for example -  if 0110110   and 1100111 are array then diff [ ] array will be -1 -1 0 0 0 0 -1

Above for loop will store index of last -1 in end[-1+n] whereas it should store index of -1 which is continuous that is end[-1+n]=1 not 6.

Please correct me if I am wrong!
0
@Tanushree Quite rare to see comment on a code :)

Actually as per question, we don't need the difference to be continuous - that will correspond to "smallest span". But we need largest span and as long as the sum is same at that index, it is fine (in between the sum difference can be any value).
+1
@Arjun Sir, in the worst case I saw it. Otherwise this question could not be solved till the Gate exam day :P

Actually I was trying dynamic programming for this question but seems like it will take me forever to do that. I understand all dp examples but could not solve new problems by using it. Any suggestions? Please help!
0

Is this algorithm dynamic programming? Anyway I did not explain it as a dynamic program solution.

When you solve a dynamic programming problem, first step is to design an algorithm without concerning the code - most times it will be just a few lines. And once you start solving, you can do all of them. Just try this one:

https://gateoverflow.in/48738/maximum-length-substring-with-k-unique-characters

First try to get a dynamic programming algorithm which can solve the problem in O(n).

0

@Arjun Sir can u say why this line?

if(start[diff[i] + n] == -1)

I mean why +n is required here?

0
@Arjun Sir

plz chk my previous command.

What +n is doing there?
+2
The difference can be from -n to +n. I'm indexing into an array using these values -- so added +n to each of them as array in C starts from 0.
0
@arjun sir

if a =0010

and b =1101

sum1 = 0

sum2 =1

diff[] = -1

sum1 = 0

sum2 = 2

diff[] = -2

sum1 = 1

sum2 = 2

diff[] = -1

sum1 = 1

sum2 = 3

diff[] = -2

is this what is done?

after this hoow is the longest span got from this logic can u explain in simple words sir
0

@arjun sir

if  a = 0010

and b = 1101

largest span = 2?

if not correct me

0
I too think this is correct

Then this can also be a discontinuous span
0
@srestha

what this algo does is.....if sum differennce is zero then keep continuing the span

if we get a difference then the span is broken...and that will be the longest span

am i right in what i infered?

It can also be discontinuos i guess

we can save the length of the longest span in max

and again start looking for another span...if that value is greater than max then again store that in max
0
Wow  ... Beautiful piece of code ... I hav come with this solution ....

main()

{

Count =0, Span_index =0 ,Span_last_found =0,Count_last_found =0;

printf("Enter n: ");
scanf("%d", &n);
for(i = 0; i < n; i++)
{
printf("Enter a[%d]: ", i);
scanf("%d", &a[i]);
}
for(i = 0; i < n; i++)
{
printf("Enter b[%d]: ", i);
scanf("%d", &b[i]);
}

for(i=0;i<n; i++)

{

if(a[i]==b[i])

{

Count++;

Span_index=i;

}

else if(Count >Count_last_found)

{

Count_last_found= Count;

Span_last_found= Span_index;

Span_index=0;

Count= 0;

}

if(count ==Span_index)

{

Print(" Span is from 0 to n-1");

}

else

{

printf(" Span is from %d to %d ", Span_last_found - Count_last_found , Count_last_found );

}

}

It will also take O(n) time ...

Correct me if i am wrong ...
0

### ARJUN Sir .... I think there is a bug in the program... but the logic is good... pls comment

0
is it possible to solve this question in real time under 3 mins during gate?? I cannot. :((((((
+4

@sushmita-It not something we have to solve. It's something we either had done before or leave it.

+1

why r u thinking, it is very tough?

Can we not think this problem as longest common subsequence problem (as, because all of then are binary number)?

+1

@srestha--But even with DP, LCS has time and space complexity of $O(mn)$ where m and n are the length of the given sequences.

0

But DP does not have linear time and space complexity with LCS.

@srestha

0

yes

then make an array of n elements and make all value initially 0.

Now where value is found , for 1st array make that position is equal to +1

And for 2nd array when value found make that position -1

At last if all values are 0, then Success

We can do this algo in O(n) time

right?

0

Can someone help me understand the logic of above code by @Arjun Sir (2nd half of the code in particular)

1. For i=0 to n-1, A[i] = A[i]-B[i]

2. Now problem has to reduced to finding longest contiguous subarray in the array A with sum=0

by Active (1.8k points)
+1
Simplest and Best explanation!!!!
0
Space O(1)??
0
Thanks man
0

2. Now problem has to reduced to finding longest contiguous subarray in the array A with difference=0 , it should be the difference, not sum.

0
+1

just giving example so that there will may not be any need to refer gfg link

A     =    1  0  1  0  1  1  0   1  0  1   0

B     =    0  0  1  0  1  1  1   1  0  1   1

A-B  =    1  0  0  0  0  0  -1  0  0  0  -1

position   1 2  3  4  5  6   7  8  9  10  11

Now there may be more that 1 continuous chain of 0 , how to find max of all of them?

take two pointer i and j . initialize i to 1

check if A-B[i] == 0 {means is this start of chain of zero} ,

if yes then do j=i & increment j till A-B[j] is 0 or j hits end of array

if A-B[j] becomes != 0 then just note max length of chain of 0 found till now i.e. j- i

also make i = j+1 so that we can find another chain of 0

if A-B[i] != 0          then increment i

If you observe carefully for every element in A we are doing comparison with that element only one time.

Hence time complexity will be linear

In example that I have given above

1. first i will be incremented to 2

2. we found A-B == 0 hence initialize j = i =2

3. increment j till A-B[j] == 0 , j will be incremented till j=7 where A-B != 0

4. Find longest sequence of 0 found till now  j - i -1  = 7-2 =  5

assign this to some variables , also assign i , j-1 to some variables

5. make i =  j+1 = 7 +1 =8

6. check A-B[i] == 0  , yes , hence make j=i

7. increment j till A-B[j] is zero , j will be incremented till j=11 , where A-B[j] != 0

8. Hence find sequence of 0 encountered till now  i.e. j - i = 11-8 = 3

9.Check if previously found sequence length is smaller that this , -> No

10.Now we also reached till end , hence max length will be 5 and span will be  2 to 6

+1

@mehul vaidya

Can u tell me one thing

Suppose, A array containing three elements 1,1,0

and B array containing 1,0,1

Will these two arrays satisfy this question or not?

Because, here $A_{i}!=B_{i}$ for A

right?

Simplest approach,

Take XNOR of two arrays, then search the largest span of 1's.

Hence space complexity = $O(3n)$ = $O(n)$  ... (one each for storing A and B and one for answer) , and

Time complexity = $O(2n)$ = $O(n)$...(first loop for XNOR, second loop for longest span of 1s)

Pseudo code:

Given: A[], B[]

for(i = 0..n)
C[i] = A[i] XNOR B[i]

max = 0;
counter = 0
for(i = 0..n)
if(C[i] == 1)
counter ++;
else
if(max < counter)
max = counter
counter = 0;        
by Active (3.6k points)
edited by
+1
This is wrong. Consider the array A [ 0 1 ] and B [ 1 0 ]. Your algorithm gives answer as 0 while there's a span of 2.
0
How can we modify if we need to check that values in span are same at each index?
+1
any 2 string which are compliment of each other, your algorithm will give span 0 where as for such string span will be n
by Boss (19.9k points)
+1 vote
@arjun  sir i think in this way we can do this. : I have not read your algorithm as it is too big. how i think i will do is.

take an array of n elements. named array.

now i will compare $A[i]=B[i]$

$array[i]=array[i-1]+a[i]$. // this will track of what is the longest sequence we have seen till now. initially i will take care of the first step.if it will be a hit then 1st location will be one else zero.

and if they are not equal just insert zero at $array[i]$. which will destroy the previous history .

and after all this in just one go i will find the largest in order of $n$.

here is the example

$10101100$

$01001100$

now the array will be  like this.

index -> $1$  $2$  $3$  $4$  $5$  $6$  $7$  $8$  $9$

value    $0$  $0$  $0$  $1$  $2$  $3$  $4$  $5$
by Boss (16k points)
edited by
0
what is largest span? difference between 2 elements in an array. So, how r u getting that?
0
it's not difference between two number. defintion is given read it .
0

is not it

Say a = 0,11,101,111,10

b=10,110,001,10,1

say if (i,j) is (1,3)

Now, how do u finding?

+1
read the question again it is saying every number is zero or one. not a combination of zero or one. it's simple zero one. we want the longest span such that the sum first array is equal to sum in second array by take the same corresponding elements..
+1
Still, only sum needs to be same - not all elements needs to be same.
0

Here the subset will be the entire array, as: a-->10101100 and b-->01001100, so a1+a2+...+a8=b1+..+b8.

So size of subset is 8, not 5.

0
@Arjun sir

do u mean span could be discontinuous too.

${\color{Blue} 1}$01${\color{Blue} 0{\color{Blue} 1{\color{Blue} 1{\color{Blue} 0{\color{Blue} 0}}}}}$

${\color{Blue} 1}$10${\color{Blue}0{\color{Blue} 1{\color{Blue} 1{\color{Blue} 0{\color{Blue} 0}}}}}$

here span will be 6

but b[i] must be equal to a[i] here

means $0{\color{Blue} 1{\color{Blue} 1{\color{Blue} 0}}}11$

and $000{\color{Blue} 1{\color{Blue} 1{\color{Blue} 0}}}$ cannot say span equal to 3 by this rt?
0
if u say only summation matter then second one also be a case, which is not acc to the question.rt sir?
0

@srestha

it says ai + ai+1.....aj

so it cannot be discontinuous

I have used dynamic programming here:

Seems like running time = O(n2) and space complexity = O(n2)

Here is the code:

#include<iostream>
using namespace std;

int main(){

int n, i, j;
int A[n], B[n];
int S1[n][n] = {0}, S2[n][n] = {0};
int span = 0;

cout<<"Enter array lengths: ";
cin>>n;
cout<<"Inputs: ";
for(i = 0; i < n; i++)
cin>>A[i]>>B[i];

for(i = 0; i <= n-2; i++){
for(j = i+1; j <= n-1; j++){
S1[i][j] = S1[i][j-1] + A[j-1];
S2[i][j] = S2[i][j-1] + B[j-1];
if(S1[i][j] == S2[i][j]){
if((j-i) > span)
span = j-i;
}
}
}

cout<<"Longest such span is "<<span;

return 0;
}


by Active (2.1k points)

Best solution is O(n)

First let c[i] = a[i] - b[i], then question become find ij, which sum(c[i], c[i+1], ..., c[j]) = 0, and max j - i.

Second let d = 0d[i + 1] = d[i] + c[i], i >= 0, then question become find ij, which d[j + 1] == d[i], and max j - i.

The value of d is in range [-n, n], so we can use following code to find the answer

answer = 0, answer_i = 0, answer_j = 0
sumHash[2n + 1] set to -1
for (x <- 0 to n) {
if (sumHash[d[x]] == -1) {
sumHash[d[x]] = x
} else {
y = sumHash[d[x]]
// find one answer (y, x), compare to current best
if (x - y > answer) {
}
}
}
by Junior (649 points)
option(c) is correct

we can simply do this by using only one for loop that will take O(n) time and space complexity=input+extra =O(n)+O(1)=O(n).. as follows:-

#include <stdio.h>
int main() {
int A={1,0,0,0,0,0,0,0,0,0};
int B={0,1,1,1,1,1,1,1,1,1};
int i,len=0,l=0;
for(i=0;i<10;i++)
{
if (A[i]==B[i])
{
len++;

}
else{

if(l<len)
{
l=len;
}
len=0;
}
}
if(l!=0)
printf("%d",l);

else
printf("no match");

return 0;

}
by (313 points)