edited by
28,462 views
66 votes
66 votes

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 by

10 Answers

Best answer
46 votes
46 votes

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 by
64 votes
64 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/

8 votes
8 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;        
edited by
1 votes
1 votes
@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
Answer:

Related questions