NEWAll India NCERT Mock Test Series is now live!Take Free Test

The World Of Algorithms

Exercise 11.2

3Questions
0%Covered
GPT Search EngineAI-Powered Search & Navigation

Search Any Question, Exercise or Concept Instantly

AI-Powered Search connects all pages for instant navigation and answers.

Problems
3 total
Q1

Suppose L1L_1 and L2L_2 are two lists of numbers in increasing order.

(i) Write an algorithm to find elements in L1L_1 that are not present in L2L_2.

(ii) Write an algorithm to find elements in L2L_2 that are not present in L1L_1.

Pending
Q2

Describe an algorithm to compute the least common multiple (lcm⁡\operatorname{lcm}) of two numbers.

Pending
Q3

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

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

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

11.3.1 Improving the Algorithm

Compute both lists of divisors together

In the algorithm above, we first check all numbers between 11 and mm to find the divisors of mm. Then we start again with 11 and check all numbers between 11 and nn to find the divisors of nn. This means we have to scan m+nm + n possible divisors. We can combine these two scans into one. Let max⁡(m,n)\max(m, n) be the maximum of mm and nn. We run through each jj from 11 to max⁡(m,n)\max(m, n).

  • If jj divides mm we add jj to the list of divisors of mm.
  • If jj divides nn we add jj to the list of divisors of nn.

This reduces the number of possible divisors to be checked from m+nm + n to max⁡(m,n)\max(m, n).

Directly compute the list of common divisors

If we combine the scans, we can directly compute the list of common divisors, instead of first computing the divisors of each number and then combining the lists.

  • For each number jj from 11 to max⁡(m,n)\max(m, n), if jj divides both mm and nn, add jj to the list of common divisors.

In fact, a common divisor cannot be larger than the smaller of the two numbers, so we can check for common divisors up to the minimum of mm and nn rather than the maximum.

  • For each number jj from 11 to min⁡(m,n)\min(m, n), if jj divides both mm and nn, add jj to the list of common divisors.

Do away with lists

Do we need to maintain the list of all common divisors? Each time we find a larger common divisor, the ones that we have found earlier are useless! Let us keep track of a quantity called most-recent-common-divisor. We know that 11 is always a common divisor, so we can start with most-recent-common-divisor set to 11. We then scan all numbers from 22 to min⁡(m,n)\min(m, n).

  • For each kk from 22 to min⁡(m,n)\min(m, n), if kk divides both mm and nn, update most-recent-common-divisor to kk.

At the end of this scan, most-recent-common-divisor directly gives us the gcd.

Pending