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)

    ReplyDelete