1. ## 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.

Thank you.

Regards,
Rayne

2. 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.

3. 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.

4. 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.
It's a similar question, but not the same. This one is much easier.

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

6. 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

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

8. 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

9. It could be that you just can't form complete sentences, and you can't spell to save your life. I mean really, can you imagine trying to parse a memo from this guy? I have a hard enough time reading his posts. Now try to get a clue as to what he's trying to say his code is doing. I mean, it's not like we're going to run out of forum space if you don't use "r" instead of "are".

Quzah.

10. 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

11. Please, those grammatical "shortcuts" of yours are not a deviated version of English. All you're doing is misspelling words intentionally. Have a look at:
http://www.catb.org/~esr/faqs/smart-...html#writewell
Particularly the first line:
We've found by experience that people who are careless and sloppy writers are usually also careless and sloppy at thinking and coding
Maybe then you'll understand.

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

13. 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;
}```

14. >>1.Arrays were not sorted arrays.So no point of ascending elements.
2.We are supposed to find the pairs(not pair) of indexs.
3.Check the complexity also.
Anyways well tried

15. 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.