Thread: O(n) algorithm

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

Think about the problem some more. They only get harder and you need to get better.

Think about the algorithm that merges two sorted lists.

See this thread. The question was asked by someone else a few days ago.

I can think of an O(n) method, but you need to make an attempt yourself.

Well, it took me about 15 seconds to think of an O(n) way for the "harder" version. :P

Originally Posted by cwr

See this thread. The question was asked by someone else a few days ago.

I can think of an O(n) method, but you need to make an attempt yourself.

Yeah, i posted one similar question like that.in which O(N) was expected.I told them my O(n) soln but they wer not satisfied with that because my soln had approx O(n) space complexity also.Even i posted my soln here but thread was deleted.If you have a better soln then post it

Originally Posted by pianorain

Let me guess...they wanted it to run in O(n) time and O(1) space?

I dont know wat exactly they want but they threw me out after this question after all they r microsoft.they want exceptinal

sorry,I forgot that i am posting on forums in which members can read hundreds of lines of code but have hard time to judge simple lingo (a little deviated version of english).I will take care for that next time.
I dont know when you will stop blaming me and answer the question.
>>Well, it took me about 15 seconds to think of an O(n) way for the "harder" version. :P

Well can you take out 50 sec more to answer this question.we will be thankful for your time

My solution takes O(n) space also, so it's probably the same, or no better than yours.

It's probably past the due date now, so I'll post some C code. Notice how the pointers walk through their arrays in the same manner that they do in mergesort, except that one walks backwards.

Code:

int is_in_sum(int v, int * A, int * B, size_t n) {
    /* Assumes A and B are in ascending order. */

    int * Ae = A + n;
    int * Bw = B + n;

    while (Bw != B) {
        -- Bw;
        while (*A + *Bw < v  &&  A != Ae) {
            ++ A;
        }

        if (*A + *Bw == v) {
            return 1;
        }
    }

    return 0;
}

In wu_weidong's problem, they are sorted, and the output is yes or no. Your problem was a different problem. The complexity of the above code is O(n) with O(1) space usage, and the point of mentioning ascending order is to point out that it's not expecting arrays sorted in descending order.