GATE CSE 2006 | Question: 54

Question

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,

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

Comments

In this question it is given that the values are binary so whatever the no. of 1 in A should be equal to the no. of 1 in B. so we can directly calculate the no. of 1 in A and which will take O(n) + O(n) right?

so option (C) is correct

---

Hashmap + Prefix Sum -> O(n) 

---

Try These algorithms problems also

Before that learn Prefix sum algorithms :   Sum( l,r ) = Prefix(r) - Prefix(l-1)

Subarray

• Subarray sum equals K
• Count subarrays divisible by K
• Longest subarray with sum K

---

Maximum Subarray

• Maximum circular subarray
• Maximum product subarray
• Maximum subarray with length constraint

---

Histogram

• Largest rectangle in histogram
• Max rectangle in binary matrix

---

2D Problems

• Maximum sum submatrix
• Count submatrix with sum K
• Maximum rectangle of 1s (Asked in jest 2026 -part B )

Answer 1

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

Comments

Even if you omit the stack space[O(m+n)], the table space required is still O(m.n) which makes the overall space complexity is O(m.n)?

---

bro haven't u seen this link ? he was talking abt tabular approach coz that's optimized one that;s why we are using memoization , or tabular approach as these are reducing the Time complexity as well as sapce too

---

nice explaination sir

Answer 2

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/

Comments

Link Given in “3. Follow http://www.geeksforgeeks.org/find-the-largest-subarray-with-0-sum/” finds continuous sub-array sum in more than O(n) hence above solution is wrong.

---

@rish-18 the given solution is correct. Even for your array it will give the correct answer,which is 10

---

A note to clear the above confusion:

Here we're finding the largest subarray with sum = 0 and not the largest subarray with contiguous 0's.

Answer 3

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;        

Comments

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.

---

How can we modify if we need to check that values in span are same at each index?

---

any 2 string which are compliment of each other, your algorithm will give span 0 where as for such string span will be n

Answer 4

Here we can use a prefix sum algorithm

like array a[0-n] and b[0-n] let n = 5

content of a = [1,0,0,1,0] and b = [1,0,1,1,0]

after applying prefix sum we will get

a =[1,1,1,2,2] b = [1,1,2,3,3] which will take O(n)

now we will compare a[n-1] and b[n-1] so here a[n-1] is smaller so we will find the a[n-1] in b if we found it we can return te largest span

Answer 5

@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$

Comments

if u say only summation matter then second one also be a case, which is not acc to the question.rt sir?

---

@srestha

it says a_i + a_i+1.....a_j

so it cannot be discontinuous

---

Thank you so much for such a simple solution to this question. Now I feel stupid for feeling confused for such a simple question. Thank you!

Answer 6

I have used dynamic programming here:

Seems like running time = O(n²) and space complexity = O(n²)

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