Confirming your payment

Skip to content

Practice Questions · Question 17 of 20

Kabir has 80 chocolate bars and 140 toffees to share into identical gift bags.

Question 173 marksMedium

Kabir has 80 chocolate bars and 140 toffees to share into identical gift bags. He already has the two lists of divisors, each in increasing order:

Two sorted lists: divisors of 80 (1, 2, 4, 5, 8, 10, 16, 20, 40, 80) and divisors of 140 (1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140)

He finds the common divisors by scanning both lists together: compare the current entry of each list; if they are equal, record the number and move on in both lists; otherwise move on in the list with the smaller entry. He stops when either list runs out. Count one comparison each time he compares two entries.

(i) Write the list of common divisors of 80 and 140.

(ii) How many comparisons does Kabir's scan make?

(iii) His friend instead takes each of the 10 entries of the first list and compares it with all 12 entries of the second list. How many comparisons is that? Why does Kabir's method need so many fewer?