## 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)