Let A1n and B1n be two arrays sorted in increasing order Ass

Let A[1..n] and B[1..n] be two arrays sorted in increasing order. Assume that both A and B have no duplicate elements. Write the pseudocode of an algorithm which computes A - B. More specifically the algorithms prints the elements which are in A and are not in B. The running time of the algorithm must be O(n).

Solution

Psuedo code(Python code):

n = len(A)
p1 = 0
p2 = 0
while((p1 < n) and (p2 < n)):
   if(A[p1] > B[p2]):
       p2 = p2 + 1
   elif(A[p1] < B[p2]):
       print A[p1],
       p1 = p1 + 1
   else:
       p1 = p1 + 1
       p2 = p2 + 1
for i in range(p1 , n):
   print A[i],

Sample Output:

A = [2,6,9,13,14,15,16,18]
B = [1,2,3,6,8,9,12,13]
A - B =[16, 18, 14, 15]

A = [2,3,4,5,6,9,13,14]
B = [1,2,3,6,7,8,9,16]
A - B =[4, 5, 14, 13]

B = [2,3,4,5,6,9,13,14]
A = [3,6,7,8,9,12,13,16]
A - B =[8, 16, 12, 7]

B = [1,2,4,5,6,8,9,13,14]
A = [1,2,3,6,7,15,16,17,18]
A - B =[3, 7, 15, 16, 17, 18]

A = [1,2,4,5,6,8,9,13,14]
B = [1,2,3,6,7,8,9,15,16]
A - B = [4, 5, 14, 13]

B = [2,3,4,5,6,9,12,13,14]
A = [1,2,3,6,7,11,16,17,21]
A - B =[1, 7, 11, 16, 17, 21]