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.
Confirming your payment
The World of Algorithms · Question 6 of 15
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.
(i) A simple algorithm, in the style of the gcd algorithm:
Start with an empty list only-in-1.
For each number in List 1: if does not appear in List 2, add to only-in-1.
Report only-in-1.
Because both lists are in increasing order, we can do better and go through each list only once, keeping a position in each list:
Start with an empty list only-in-1. Let be the first element of List 1 and the first element of List 2.
If List 2 is finished, add and all the remaining elements of List 1 to only-in-1, and go to Step 6.
If : cannot appear later in List 2 (the later elements are even larger), so add to only-in-1 and move to the next element of List 1.
If : is present in List 2, so move to the next element of List 1 and to the next element of List 2.
If : move to the next element of List 2.
After doing whichever one of Steps 3, 4 and 5 applies, repeat from Step 2 until List 1 is finished.
Report only-in-1.
Example. List 1 (the divisors of 375) and List 2 (the divisors of 825).
Result: elements of List 1 not in List 2 .
(ii) This is the same algorithm with the roles of the two lists exchanged:
Start with an empty list only-in-2. Let be the first element of List 2 and the first element of List 1.
If List 1 is finished, add and all the remaining elements of List 2 to only-in-2, and go to Step 6.
If : add to only-in-2 and move to the next element of List 2.
If : move both and to the next elements of their lists.
If : move to the next element of List 1.
After doing whichever one of Steps 3, 4 and 5 applies, repeat from Step 2 until List 2 is finished.
Report only-in-2.
With the same two lists (now scanning List 2 against List 1):
Result: elements of List 2 not in List 1 .
Each step moves forward in at least one list, so the scan takes at most (length of List 1 + length of List 2) comparisons, instead of searching the whole of List 2 for every element of List 1.