Spanning array

Computer Science Level 4

Given two binary arrays $A$ and $B$ (consisting of 1 and 0 only), a $\text{span}(i,j)$ is defined for $i\leq j$ , where:

$A[i]+A[i+1]+\cdots + A[j]=B[i]+B[i+1]+\cdots + B[j]$

What is the length of the longest $\text{span}(i,j)$ in the two arrays shown in the text file?

Details and Assumptions :

For $A=[0, 1, 0, 0, 1]$ and $B=[1, 0, 0, 1, 1]$ , the longest span is of length 4: index 1 to 4. ( with $0$ indexing)
For $A=[0, 0, 0, 0, 0]$ and $B=[1, 1, 1, 1, 1]$ , the longest span is of length 0.

The answer is 568.

3 solutions

Arkajyoti Banerjee
Dec 24, 2017

Quicker?

/* Helper Function: Returns sum of elements in A from index i to j */
int sum(int A[], int i, int j)
{
    int s = 0; 
    for(int k = i; k <= j; k++)
        s += A[k];
    return s;
}

int longestSpan(int A[], int B[], int N)
{
    for(int i = 0; i < N; i++)
            for(int j = 0; j <= i; j++)
                if(sum(A, j, N - 1 - i + j) == sum(B, j, N - 1 - i + j))
                    return N - i;
}

Mehdi K.
May 22, 2016

Python3

>>> def looon(A1, A2):
...     L=min(len(A1), len(A2))              #Just incase they do not have the same length
...     return max(j-i+1 for i in range(L) for j in range(i,L) if sum(A[i:j+1])==sum(B[i:j+1]))
... 
>>> looon(A, B)
568

A Former Brilliant Member
May 18, 2016

Python 3.5.1:

#Spanning array
#18/5/2016
def solve(array1,array2):
    runningmax = 0
    for i in range(1,len(array1)):
        for j in range(i,len(array1)):
            if sum(array1[x] for x in range(i,j+1))==sum(array2[x] for x in range(i,j+1)):
                if j-i+1>runningmax:
                    runningmax=j-i+1
    return runningmax

Spanning array

The answer is 568.

3 solutions

0 pending reports