NCERT Solutions for Class 9 Maths Chapter 11 — Exercise Set 11.2#

An algorithm is written as numbered steps, using names for the values we keep track of (such as list-of-divisors) and simple actions we already know how to do (such as checking whether one number divides another).

1. 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.

Algorithm only-in-1

  1. Start with an empty list called only-in-1.
  2. For each number $x$ in List 1:
    • if $x$ does not appear in List 2, add $x$ to only-in-1.
  3. Report only-in-1.

Example: List 1 = [1, 3, 5, 15], List 2 = [1, 5, 11]. Checking 1 (in List 2), 3 (not), 5 (in), 15 (not) gives only-in-1 = [3, 15].

Using the order (faster): because both lists are increasing, we can walk through them together. Keep a position in each list. If the current number in List 1 is smaller than the one in List 2, it is not in List 2 — add it and move on in List 1. If they are equal, skip it and move on in both. If List 2’s number is smaller, move on in List 2. When List 2 runs out, every remaining number in List 1 is added. This looks at each number only once.

(ii) Write an algorithm to find elements in List 2 that are not present in List 1.

It is the same algorithm with the two lists swapped:

  1. Start with an empty list called only-in-2.
  2. For each number $y$ in List 2:
    • if $y$ does not appear in List 1, add $y$ to only-in-2.
  3. Report only-in-2.

With the example above, only-in-2 = [11].

2. Describe an algorithm to compute the least common multiple (lcm) of two numbers. #

Algorithm 1 : from the definition

The lcm of $m$ and $n$ is the smallest number that both divide. It is at most $m \times n$, and it is a multiple of the larger number.

Algorithm lcm(m, n)

  1. Let big be the larger of $m$ and $n$, and small the other.
  2. For each $k = 1, 2, 3, \ldots, \text{small}$:
    • if small divides $k \times \text{big}$, report $k \times \text{big}$ as lcm(m, n) and stop.

Example: lcm(6, 8): big = 8, small = 6. $8$: 6 does not divide it. $16$: no. $24$: yes, so lcm(6, 8) = 24.

The loop always stops by $k = \text{small}$, because small divides $\text{small} \times \text{big}$.

Algorithm 2 : using the gcd

For any two numbers, $\text{gcd}(m, n) \times \text{lcm}(m, n) = m \times n$. So:

  1. Compute $g = \text{gcd}(m, n)$ (using any gcd algorithm in the chapter).
  2. Report $\dfrac{m \times n}{g}$ as lcm(m, n).

Example: gcd(6, 8) = 2, so lcm(6, 8) $= \dfrac{48}{2} = 24$. This is much faster for large numbers, because Āryabhaṭa’s algorithm finds the gcd quickly.

*3. Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6). #

(i) If we write out divisors in pairs, how many numbers do we have to examine between 1 and n to find all the divisors of n?

In every pair $(d, \dfrac{n}{d})$, the smaller number is at most $\sqrt{n}$ (if both were bigger than $\sqrt{n}$, their product would be bigger than $n$). So it is enough to check $j = 1, 2, \ldots$ up to $\sqrt{n}$: each time $j$ divides $n$, we get the pair $(j, \dfrac{n}{j})$.

∴ We only need to examine about $\sqrt{n}$ numbers instead of $n$. For example, for 10000 we check 1 to 100 instead of 1 to 10000.

(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?

Not directly. The gcd algorithm reports the rightmost element of the list of common divisors as the gcd. That works only because the divisor lists are in increasing order.

If we collect divisors in pairs, the list comes out mixed up, for example [1, 18, 2, 9, 3, 6] for 18. The common divisors would then not be in increasing order, and the rightmost one need not be the largest.

Fix: either sort the list of divisors into increasing order before comparing (smaller divisors in order, then the partners in reverse order), or change the last step to “report the largest element of common-divisors”.

Quick links