Hi all,

I am supposed to design an O(n) algorithm that solves the following problem.

Input: An integer v and 2 sorted arrays A and B, each having n integers.

Output: Yes if and only if there exist i and j such that v = A[i] + B[j].

No if no such i and j exist.

The algorithms I came up with were linear search, which gave O(n^2) and binary search, which gave O(n log n). None gave me an O(n) algorithm.

Please help.

Thank you.

Regards,

Rayne