Anonymous user menu

Find the largest span of two arrays using Bit Algorithms.

Given two arrays of numbers a1, a2, a3,...an and b1, b2, .. bn where each number is 0 or 1, the fastest algorithm to find the largest span(i, j) such that ai + ai+1, ....aj = bi + bi+1, .. bj. or report that there is not such span,

A

Takes O(n3) and Ω(2n) time if hashing is permitted

B

Takes O(n3) and Ω(n2.5) time in the key comparison model

C

Takes θ(n) time and space

D

Takes O(√n) time only if the sum of the 2n elements is an even number

0Comment