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

+4

A good video for explanation-  .

8 Answers

+27 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 (408k points)
edited by
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. :((((((
+1

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

+1

@Ayush Upadhyaya

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

@Ayush Upadhyaya

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)

+13 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.7k points)
0
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
This is called The Answer
0

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[2] == 0 hence initialize j = i =2

3. increment j till A-B[j] == 0 , j will be incremented till j=7 where A-B[7] != 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

 

+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
+3 votes
Answer is C.
answered 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$
answered by Boss (15.9k 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

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 by Active (1.9k points)
0 votes

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) {
      answer = x - y
      answer_i = y
      answer_j = y
    }
  }
}
answered by Junior (637 points)
0 votes
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[10]={1,0,0,0,0,0,0,0,0,0};
    int B[10]={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;

}
answered by (253 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
49,548 questions
54,174 answers
187,486 comments
71,129 users