🌐 All Subjects 🔬 Science 🌍 Social Science 📐 Mathematics 📖 English 🪶 हिन्दी
← Back to Chapter 11 Exercises

⚙️ Chapter 11: The World of Algorithms • Exercise Set 11.3

Verified step-by-step solutions for your class notes.

Exercise Set 11.1 5Exercise Set 11.2 3Exercise Set 11.3 2End-of-Chapter Exercises 5All Exercises 15
Q1

How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1?

Answer: The list of divisors would be generated in strictly decreasing order instead of increasing order. Consequently, the list of common divisors would also be in decreasing order. Therefore, Step 5 of the original algorithm would need to change: instead of reporting the rightmost element (which would now be 1), it must report the leftmost element (the first and largest common divisor found).

Q2

What about the last algorithm described above? What happens when we look at common divisors starting from $min(m, n)$ and work backwards to 1?

Answer: If we start from $min(m, n)$ and work backwards to 1, the very first common divisor we encounter will be the greatest common divisor. This drastically improves efficiency because we can stop the loop immediately upon finding the first number that divides both m and n, rather than scanning all the way to $min(m,n)$ and constantly updating the most-recent-common-divisor.