Given a number X , find two elements in two sorted arrays such A[i]+B[j] = X in O(n+m)

Question

Given the following problem , I'd appreciate for any corrections since I have no solution for the current question (taken from one of my professor's exams !!!) :

Remark: this is no homework !

Problem:

Given two sorted arrays A (with length n) & B (with length m) , where each

element (in both arrays) is a real number , and a number X (also a real number) ,

we'd like to know whether or not exists a ∈ A and b ∈ B , such as :

a + b = X , in O(n+m) running time .

Solution :

First , we start to check from the end of both arrays , since we don't need the numbers that are bigger than X :

• i = n

• k = m

• while A[i] > X , i = i -1

• while B[k] > X , k = k -1

Define j = 0 . Now start running from the current i in A , and from j in B :

• while i > 0 , j < k :
• if A[i]+B[j] == X , then return both cells
• else j = j+1 , i = i -1

In the end we'd have either the two elements , or we'd reach out of bounds in one or both of the arrays , which means that no two elements such a + b = X are indeed exist .

Any remarks would be much appreciated

Thanks

Answer 1

You shouldn't adjust i and j at the same time. If the sum is too big, you should decrease i. If it is too small, increase j.

Answer 2

This problem is a special case of the following question: Find number in sorted matrix (Rows n Columns) in O(log n)

Consider a matrix filled with the C[i,j] = A[i] + B[j], then starting from one of the corners, you decrease i if the sum is too big, and if it's too small, increase j. Of course you don't have to create and/or fill this matrix C in your program, just assume you know any element of this matrix: it's A[i] + B[j], you can compute it immediately at any moment. The resulting algorithm is O(m+n).

Answer 3

I have the same question for homework. I worked out before I check it on the internet. Here is my solution(Python), hope some big guys see it and help me to improve it

# 1.3. Given two sorted arrays a and b and number S. Find two elements such that sum a[i] + b[j] = S.Time O(n).

def find_elem_sum(alist, blist, S): # O(n)

if alist is None or alist == [] or blist is None or blist == []:
    return None

# find the numbers which are less than S in the lists
#
#
# pretend it is done

a_length = len(alist)
b_length = len(blist)
a_index, b_index = 0, 0
count = 0
while alist and a_index < a_length and b_index < b_length:
    count += 1
    if alist[a_index] + blist[b_index] < S:
        if a_index < a_length - 1:
            a_index += 1
        if a_index == a_length - 1:
            b_index += 1;
        continue
    elif alist[a_index] + blist[b_index] > S:
        alist = alist[:a_index]
        a_length = len(alist)
        a_index = a_length - 1
    elif alist[a_index] + blist[b_index] == S:
        return [a_index, b_index, count]

return None