4.2k 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 | 4.2k 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
+2

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");
}
}

edited
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?
+1
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

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

0
Simplest and Best explanation!!!!
0
Space O(1)??
0
Thanks man

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;        
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
+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$
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[5] = 0,11,101,111,10

b[5]=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

Take an additional array of numbers say
C [1..N].       // Tetha(N) additional space

For i = 1 to N
{
C[ i ] = a [ i ] xor b [ i ]
}
//Tetha(N) time complexity

Check for largest sequence of 0's in C and retrieve corresponding indices in either a or b
// Can be done in Tetha(N)

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;
}


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[0] = 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) {
}
}
}

1
2