The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+37 votes
3.9k 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
asked in Algorithms by Active (3.7k points)
edited by | 3.9k 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$.

+1

A good video for explanation-  .

7 Answers

+21 votes
Best answer

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");
    }
}
answered by Veteran (359k points)
edited by
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
Added the new algo :)
+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
Added :)
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?
+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?

is this what is asked?

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 ...
+7 votes

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;        
answered by Active (3.5k 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
+4 votes

Answer -> C

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

3. Follow http://www.geeksforgeeks.org/find-the-largest-subarray-with-0-sum/

answered by Active (1.5k points)
+3 votes
Answer is C.
answered by Boss (19.7k 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$
answered 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[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

0 votes
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)
answered by (53 points)
0 votes

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

 

answered ago by Active (1.3k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,082 questions
47,675 answers
147,478 comments
62,393 users