PA of Algorithms Q97

97Given two arrays of numbers a₁,..., a_n and b₁,...,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+i +....+ a_j = b_i + b_i+i +....+ b_j or report that there is no such span,

Option : C
Explanation :
a₁, a₂ .....................a_n
b₁, b₂ .....................b_n
In order to find out the largest span, check the sums of
a_i +............a_j and b_i +..............b_j at each step.
If a₁ + a₂ = b₁ + b₂ go on, check a₁ + a₂ + a₃ and b₁ + b₂ + b₃.
If not, then check a₂ + a₃ and b₂ + b₃
Similarly a check is done at each of the n places during traversal. A separate variable has to be kept that contains the maximum span observed hitherto
Hence fastest algorithm computes with (~) (n) time and space.

Forgot your password?

I agree with the Terms.