Algorithms · 4 marks

Suppose List 1 and List 2 are two lists of numbers in increasing order.

(i) Write an algorithm to find elements in List 1 that are not present in List 2.
(ii) Write an algorithm to find elements in List 2 that are not present in List 1.

Answer: (i) Start with an empty list; for each x in List 1, if x does not appear in List 2, add x to it; report the list. (ii) The same with the two lists swapped. For List 1 = divisors(375), List 2 = divisors(825): (i) [125, 375], (ii) [11, 33, 55, 165, 275, 825].

Step-by-step solution

Idea: Use the same pattern as the list of common divisors: start with an empty list and go through one list element by element, but keep an element when it is not found in the other list. Because both lists are in increasing order, the answer list is also in increasing order.

(i) Write an algorithm to find elements in List 1 that are not present in List 2.

Give the answer list a name so we can refer to it: only-in-1. Step 1: start with only-in-1 empty, [ ].½ mark
Step 2: for each number x in List 1 (from left to right): if x does not appear in List 2, add x to the end of only-in-1.1 mark
Step 3: report only-in-1. Example: List 1 = [1, 3, 5, 15, 25, 75, 125, 375], List 2 = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]. Only 125 and 375 are missing from List 2, so only-in-1 = [125, 375].½ mark
Faster, using the increasing order: keep a marker on List 2 that only moves right. For each x in List 1, move the marker past every number smaller than x. If the marker’s number equals x, x is in List 2; otherwise x is not, so add it. Each list is then read only once, instead of searching the whole of List 2 for every x.

Start with an empty list only-in-1; for each x in List 1, if x does not appear in List 2, add x to only-in-1; report only-in-1.

(ii) Write an algorithm to find elements in List 2 that are not present in List 1.

This is the same task with the roles of the lists swapped. Step 1: start with an empty list only-in-2 = [ ].½ mark
Step 2: for each number y in List 2: if y does not appear in List 1, add y to the end of only-in-2.1 mark
Step 3: report only-in-2. With the same two lists: 11, 33, 55, 165, 275 and 825 are not in List 1, so only-in-2 = [11, 33, 55, 165, 275, 825].½ mark

Start with an empty list only-in-2; for each y in List 2, if y does not appear in List 1, add y to only-in-2; report only-in-2.

(i) For each x in List 1, add x to a new list if x is not in List 2. (ii) For each y in List 2, add y to a new list if y is not in List 1. Both answer lists come out in increasing order.

Check: Every element of List 1 is either common to both lists or in only-in-1: common [1, 3, 5, 15, 25, 75] (6 numbers) + [125, 375] (2) = 8 = length of List 1 ✓. Likewise 6 + 6 = 12 = length of List 2 ✓.

Answer to write in the exam

(i)

only-in-1 = [ ]

For each x in List 1:

– if x does not appear in List 2, add x to only-in-1

Report only-in-1

e.g. List 1 = divisors(375), List 2 = divisors(825) → only-in-1 = [125, 375]

(ii)

only-in-2 = [ ]

For each y in List 2:

– if y does not appear in List 1, add y to only-in-2

Report only-in-2

e.g. List 1 = divisors(375), List 2 = divisors(825) → only-in-2 = [11, 33, 55, 165, 275, 825]

Common mistakes that cost marks

Writing “remove the common numbers” without saying how: an algorithm must give exact steps (start empty, check each element, add if missing).
Reversing the condition and collecting the common elements instead of the missing ones.
Forgetting to start the answer list empty, or forgetting to report it at the end.

How this can come in the exam

MCQ (1 mark)

List 1 = [2, 4, 6, 8, 10] and List 2 = [3, 6, 9, 12]. The algorithm for elements of List 2 that are not present in List 1 reports

[2, 4, 8, 10]
[3, 9, 12]
[6]
[3, 6, 9, 12]

Show answer

(B) [3, 9, 12]
Of 3, 6, 9, 12, only 6 is in List 1. So the answer is [3, 9, 12].

Try one yourself

List 1 = [1, 2, 4, 8, 16] and List 2 = [1, 2, 3, 4, 6, 12]. Find (i) the elements of List 1 not in List 2, (ii) the elements of List 2 not in List 1.