Ex 11.2 Class 9 Maths Ganita Manjari Solutions | Sid Classes
Welcome to Sid Classes, your trusted destination for comprehensive academic resources! In this detailed study guide, we present complete, step-by-step solutions for the NCERT Class 9 Maths Ganita Manjari Chapter 11 Exercise 11.2 Advanced Algorithms, List Comparisons, and Divisor Pairs. Designed to reflect how top-scoring students write their solutions and reasoning in school examinations, this walkthrough covers sorted list traversal algorithms, least common multiple (LCM) computations, and square-root optimization for divisor pairs entirely clear.
🔑 Key Concepts & Algorithmic Principles:
- Two-Pointer List Comparison: Efficiently finding set differences between two sorted lists in linear time \(O(n + m)\).
- Divisor Pairing Optimization: Reducing trial division checks from \(n\) down to \(\sqrt{n}\) by utilizing divisor pairs \((d, n/d)\).
NCERT Class 9 Maths Ganita Manjari Chapter 11 Exercise 11.2 Solutions
Question 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.
(ii) Write an algorithm to find elements in List 2 that are not present in List 1.
Solution:
Since both lists are already sorted in increasing order, we can use a highly efficient two-pointer algorithm without needing nested loops.
(i) Algorithm for elements in List 1 not in List 2:
1. Initialize pointer \(i = 0\) for List 1 and pointer \(j = 0\) for List 2.
2. While \(i\) is less than the length of List 1 and \(j\) is less than the length of List 2:
* If \(\text{List}_1[i] < \text{List}_2[j]\), then \(\text{List}_1[i]\) is not in List 2. Add \(\text{List}_1[i]\) to the result list and increment \(i\).
* If \(\text{List}_1[i] == \text{List}_2[j]\), the element is present in both lists. Increment both \(i\) and \(j\).
* If \(\text{List}_1[i] > \text{List}_2[j]\), increment \(j\) to catch up in List 2.
3. If any elements remain in List 1 after List 2 is exhausted, add all remaining elements of List 1 to the result.
(ii) Algorithm for elements in List 2 not in List 1:
1. Swap the roles of the pointers or lists: initialize pointers \(i = 0\) for List 1 and \(j = 0\) for List 2.
2. While traversing both lists, if \(\text{List}_2[j] < \text{List}_1[i]\), add \(\text{List}_2[j]\) to the result and increment \(j\).
3. If equal, increment both \(i\) and \(j\). If \(\text{List}_2[j] > \text{List}_1[i]\), increment \(i\).
4. Add any leftover elements of List 2 to the result.
Question 2
Describe an algorithm to compute the least common multiple (lcm) of two numbers.
Solution:
The least common multiple (\(\text{LCM}\)) of two positive integers \(a\) and \(b\) can be efficiently computed using their greatest common divisor (\(\text{GCD}\)) based on the standard mathematical relationship: \(\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}\).
Algorithm Steps:
1. Input two numbers \(a\) and \(b\).
2. Compute \(\text{GCD}(a, b)\) using the Euclidean algorithm (repeated division remainder method).
3. Multiply \(a\) and \(b\), then divide the product by \(\text{GCD}(a, b)\).
4. Output the resulting value as \(\text{LCM}(a, b)\).
Question 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\)?
(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?
Solution:
(i) Number of checks required:
We only need to examine numbers from \(1\) up to \(\sqrt{n}\). If \(d\) is a divisor of \(n\) within this range, then its paired divisor is \(n/d\). Checking up to \(\sqrt{n}\) finds all divisor pairs without needing to test up to \(n\).
(ii) Impact on GCD algorithm:
While listing divisor pairs helps find all factors of individual numbers efficiently, standard GCD algorithms (such as the Euclidean algorithm) rely on successive remainders rather than full factor listing. Therefore, the Euclidean algorithm remains much faster and operates independently of divisor pairing methods.
Frequently Asked Questions (FAQs)
Q1: Why is the two-pointer approach efficient for sorted lists?
A: It processes each element at most once, achieving a linear time complexity of \(O(n + m)\) compared to \(O(n \times m)\) for nested searches.
Q2: How does the square root bound optimize divisor searching?
A: Because factors always appear in complementary pairs around \(\sqrt{n}\), checking beyond \(\sqrt{n}\) is redundant.
Quick Navigation:
Last updated according to the latest NCERT Ganita Manjari syllabus.