Tuesday, December 14, 2010

K-th sum for two sorted arrays

You are given 2 arrays A, B sorted in decreasing order of size m and n respectively and a number k, such that 1 <= k <= m*n. You need to fine the kth largest sum(a+b) possible where a \in A, and b \in B.

Hint: i like this problem, a possible solution is by induction and the complexity is O(n+m).

1 comment:

  1. This problem is intriguing, and very related to open problems in computational geometry (as far as I know).
    I found something I think is optimal but can't prove it yet (not based on induction and not elegant).
    So... didn't find the solution yet.

    Keep up posting these interesting games!

    Maurizio (from Cagliari)