Confirming your payment

Skip to content

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

A school has 391 boys and 299 girls to form identical sports teams (the most teams possible, each with the same…

Question 332 marksHard

A school has 391 boys and 299 girls to form identical sports teams (the most teams possible, each with the same numbers of boys and of girls). Three apps find gcd⁡(391,299)\gcd(391, 299). App 1 uses most-recent-common-divisor, checking k=2,3,…,299k = 2, 3, \ldots, 299. App 2 uses Euclid's subtraction algorithm. App 3 uses Āryabhaṭa's division algorithm. Count one check for each kk, and one reduction for each use of Step 3.

(i) How many values of kk does App 1 check? How many reductions does App 2 make?

(ii) Trace App 3, say which app does the least work, and describe the teams.