Given two arrays of numbers a₁,...,aₙ and b₁,...,bₙ, where each number is 0 or…
GATE · 2006 · CS
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,
- A.
Takes O(3ⁿ) and Ω(2ⁿ) time if hashing is permitted
- B.
Takes O(n³) and Ω(n²·⁵) 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
Attempted by 13 students.
Sign up free to check your answer
Sign up freeLoading lesson…