Given two arrays of numbers a₁,...,aₙ and b₁,...,bₙ, where each number is 0 or…

PYQ GATE 2006

Given two arrays of numbers a₁,...,aₙ and b₁,...,bₙ, where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that aᵢ + aᵢ₊₁ + ... + aⱼ = bᵢ + bᵢ₊₁ + ... + bⱼ, or report that there is not such span,

  1. A.

    Takes O(3ⁿ) and Ω(2ⁿ) time if hashing is permitted

  2. B.

    Takes O(n³) and Ω(n²·⁵) time in the key comparison model

  3. C.

    Takes Θ(n) time and space

  4. D.

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

Attempted by 84 students.

Sign up free to check your answer

Sign up free

Explore the full course: Data Structures

Loading lesson…