6

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

JAN
  • 21,236
  • 66
  • 181
  • 318
  • maybe you can write down your entire algorithm in pseudo-code. The mix between english and pseudo-code confuses me. – Marijn van Vliet Jun 27 '12 at 14:35
  • 1
    Notice that you can omit the preprocessing. You can leave decrementing i to the main loop, and for j use a suitable loop condition (j ≤ m and B[j] ≤ X). You should not do any such optimization in cases where negative numbers are allowed in the arrays. – MvG Jun 27 '12 at 14:42

3 Answers3

12

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.

MvG
  • 57,380
  • 22
  • 148
  • 276
  • Great thing to notice. However, doesn't this still lead to an O(n*m) solution? – BlackVegetable Jun 27 '12 at 14:36
  • 1
    @BlackVegetable: O(n+m) it was, and yes, it does. At each step you move in one array *or* the other array, so combined you cannot move more ofthen than the sum of both array lengths. – MvG Jun 27 '12 at 14:37
4

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

Community
  • 1
  • 1
unkulunkulu
  • 11,576
  • 2
  • 31
  • 49
1

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
Guan
  • 21
  • 2