Confirming your payment

Skip to content

Competency-Based Questions (CBQ) · Question 20 of 40

A coding club holds an "algorithm race".

Question 204 marksMedium

A coding club holds an "algorithm race". Each team must find gcd⁡(96,132)\gcd(96, 132) to pack 96 apples and 132 bananas into identical fruit baskets, and the team that checks the fewest numbers wins. Team 1 uses the first gcd algorithm and counts the divisibility checks made while listing the divisors of 96 and of 132. Team 2 checks each jj from 1 to min⁡(96,132)\min(96, 132). Team 3 checks k=96,95,94,…k = 96, 95, 94, \ldots downwards and stops at the first kk dividing both, counting that kk too.

Table of the three teams and their methods with an empty checks column

(i) How many divisibility checks does Team 1 make?

(ii) How many numbers does Team 2 check?

(iii) At which kk does Team 3 stop, how many numbers does it check, and which team wins?