“Ch 11 The World of Algorithms Solutions Class 9“ is prepared on the basis on Ganita Manjari Part 2 class 9 NCERT.
The solutions are created after the lots of discussions in live classes.
“Ch 11 The World of Algorithms Solutions Class 9“ is strictly based on Ganita Manjari Grade 9 NCERT textbook.
The actual classroom solutions are not possible to upload here as they are very detailed and explanatory.
Yet,
We have tried to strike a balance between the solution and explanations.
For any further assistance on any question please contact us.
For more chapter solutions | Class 9 Maths Solutions
Exercise Set 11.1
Q1.
Add two 4-digit numbers using the steps we have written down. Make sure you follow the steps precisely; do not perform any action that is not explicitly mentioned. Are you able to obtain the
correct result?
Solution:
Execute
Take 5847 + 2698 and follow the steps exactly.
| 1 | 1 | 1 | ||
| 5 | 8 | 4 | 7 | |
| + | 2 | 6 | 9 | 8 |
| 8 | 5 | 4 | 5 |
Ones: 7 + 8 = 15, write 5, carry 1.
Tens: 4 + 9 + 1 = 14, write 4, carry 1.
Hundreds: 8 + 6 + 1 = 15, write 5, carry 1.
Thousands: 5 + 2 + 1 = 8, write 8, carry 0.
Result: 8545, which is correct.
Now
Try 3764 + 2346. Ones: 4 + 6 = 10.
10 is not “less than 10” and not “more than 10”.
The steps do not say what to do.
Fix: use “10 or more”. Then 3764 + 2346 = 6110.
Correct result for 5847 + 2698: 8545.
Gap: a column sum of exactly 10.
Fix: “10 or more” gives carry 1.
Q2.
What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?
Solution:
Example
Add 45978 + 345. Align right to left.
| 1 | 1 | 1 | |||
| 4 | 5 | 9 | 7 | 8 | |
| + | 3 | 4 | 5 | ||
| 4 | 6 | 3 | 2 | 3 |
Ones: 8 + 5 = 13, write 3, carry 1.
Tens: 7 + 4 + 1 = 12, write 2, carry 1.
Hundreds: 9 + 3 + 1 = 13, write 3, carry 1.
Thousands: 5 + ? + 1. The second number has no digit here.
Treat empty places as 0. Thousands: 5 + 0 + 1 = 6, carry 0.
Ten-thousands: 4 + 0 + 0 = 4.
Not handled as written, since a column has one digit.
Fix: pad with zeros.
45978 + 345 = 46323.
Q3.
Why is it important to align the columns from right to left?
Solution:
Idea
Each column has one place value: units, tens, hundreds.
Only digits of the same place value can be added.
Example
Add 345 + 27.
Right aligned: 5 + 7, 4 + 2, 3 gives 372. Correct.
Left aligned: 27 is read as 270, so we get 615. Wrong.
Right alignment pairs units with units, tens with tens.
Carries move left, so we start from the right.
Q4.
In Step 3, why cannot the value of carry be more than 1?
Solution:
Claim
In every column, the carry is 0 or 1.
Largest digit is 9.
Step 2: 9 + 9 = 18, so the carry is at most 1.
Step 3: 9 + 9 + 1 = 19.
19 < 20, so the tens part of the sum is at most 1.
Largest possible sum is 19, which is less than 20.
So carry is never more than 1.
Q5.
What happens if we do not include the fifth step in the algorithm
above? Give examples where the algorithm will work correctly
and where it will fail to work.
Solution:
Where it works
The last column gives no carry.
123 + 456 = 579. Step 5 is not needed.
Where it fails
The last column gives carry 1. Take 85 + 47.
Ones: 5 + 7 = 12, write 2, carry 1.
Tens: 8 + 4 + 1 = 13, write 3, carry 1.
No digits are left. Without Step 5 we get 32.
With Step 5, write 1 on the left: 132.
Works when the final carry is 0: 123 + 456 = 579.
Fails when the final carry is 1: 85 + 47 gives 32, not 132.
Exercise Set 11.2
Q1.
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:
Part (i)
1. Start with an empty list only-in-List 1.
2. For each x in List 1: if x does not appear in List 2, add x to only-in-List 1.
3. Report only-in-List 1
Part (ii)
Swap the roles. Start with an empty list only-in-List 2.
For each x in List 2: if x does not appear in List 1, add x to only-in-List 2.
Example
List 1 = [1, 3, 5, 15, 25, 75, 125, 375]
List 2 = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]
(i) only-in-List 1 = [125, 375]
(ii) only-in-List 2 = [11, 33, 55, 165, 275, 825]
(i) Keep x of List 1 that is missing from List 2.
(ii) Same, with the two lists swapped.
Q2.
Describe an algorithm to compute the least common multiple (lcm) of two numbers.
Solution:
Algorithm
1. Let multiple = max(m, n).
2. If both m and n divide multiple, report multiple as the LCM.
3. Otherwise, add max(m, n) to multiple and go back to Step 2.
Example
multiple = 18: 12 does not divide 18.
multiple = 36: 12 and 18 both divide 36.
LCM(12, 18) = 36
Test the multiples of max(m, n) in order.
The first one divisible by both is the LCM.
Q3.
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:
Part (i)
Divisors come in pairs (j, n/j).
One number of each pair is at most √n.
So check only j = 1 to √n. Partners come free as n/j.
n = 18: √18 ≈ 4.2, so check 1 to 4 only.
1 → (1, 18); 2 → (2, 9); 3 → (3, 6); 4 does not divide.
Part (ii)
Pairs give [1, 18, 2, 9, 3, 6]. This is not in increasing order.
Pair lists for 375 and 825:
[1, 375, 3, 125, 5, 75, 15, 25]
[1, 825, 3, 275, 5, 165, 11, 75, 15, 55, 25, 33]
Common: [1, 3, 5, 75, 15, 25]. Rightmost is 25, but gcd is 75.
(i) About √n numbers need checking, not n.
(ii) Not as described. Report the largest common divisor, not the rightmost.
Exercise Set 11.3
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?
Solution:
Check j from n down to 1.
Now divisors(n) is in decreasing order. Example: divisors(18) = [18, 9, 6, 3, 2, 1].
Common divisors, built in this order, are also decreasing.
So the largest is the leftmost element.
Only Step 5 changes: report the leftmost element of common-divisors.
Example: gcd(375, 825)
divisors-of-m = [375, 125, 75, 25, 15, 5, 3, 1]
common-divisors = [75, 25, 15, 5, 3, 1]
Leftmost is 75.
Only Step 5 changes.
Report the leftmost element, not the rightmost.
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?
Solution:
Scan k from min(m, n) down to 1.
1. For each k from min(m, n) down to 1:
2. If k divides both m and n, report k as the gcd and stop.
Examples
m = 6, n = 12: k = 6 divides both. gcd = 6 in 1 check.
The old scan from 2 up needed 5 checks.
m = 8, n = 15: k = 8, 7, …, 2 all fail. k = 1 works. gcd = 1.
The first common divisor found is the gcd.
We stop at once, with no need to keep updating.
End-of-Chapter Exercises
Q1.
Compute the following using the improved version of Euclid’s algorithm.
(i) gcd(375, 825)
(ii) gcd(51000, 81000)
(iii) gcd(1789287, 237656)
(iv) gcd(2587392, 157656)
Solution:
Part (i)
375 < 825, so reverse: gcd(825, 375).
| gcd(m, n) | m = q × n + r | r = m mod n |
|---|---|---|
| gcd(825, 375) | 825 = 2 × 375 + 75 | 75 |
| gcd(375, 75) | 375 = 5 × 75 + 0 | 0 |
n = 0, so gcd(75, 0) = 75.
Part (ii)
51000 < 81000, so reverse: gcd(81000, 51000).
| gcd(m, n) | m = q × n + r | r = m mod n |
|---|---|---|
| gcd(81000, 51000) | 81000 = 1 × 51000 + 30000 | 30000 |
| gcd(51000, 30000) | 51000 = 1 × 30000 + 21000 | 21000 |
| gcd(30000, 21000) | 30000 = 1 × 21000 + 9000 | 9000 |
| gcd(21000, 9000) | 21000 = 2 × 9000 + 3000 | 3000 |
| gcd(9000, 3000) | 9000 = 3 × 3000 + 0 | 0 |
n = 0, so gcd(3000, 0) = 3000.
Part (iii)
| gcd(m, n) | m = q × n + r | r = m mod n |
|---|---|---|
| gcd(1789287, 237656) | 1789287 = 7 × 237656 + 125695 | 125695 |
| gcd(237656, 125695) | 237656 = 1 × 125695 + 111961 | 111961 |
| gcd(125695, 111961) | 125695 = 1 × 111961 + 13734 | 13734 |
| gcd(111961, 13734) | 111961 = 8 × 13734 + 2089 | 2089 |
| gcd(13734, 2089) | 13734 = 6 × 2089 + 1200 | 1200 |
| gcd(2089, 1200) | 2089 = 1 × 1200 + 889 | 889 |
| gcd(1200, 889) | 1200 = 1 × 889 + 311 | 311 |
| gcd(889, 311) | 889 = 2 × 311 + 267 | 267 |
| gcd(311, 267) | 311 = 1 × 267 + 44 | 44 |
| gcd(267, 44) | 267 = 6 × 44 + 3 | 3 |
| gcd(44, 3) | 44 = 14 × 3 + 2 | 2 |
| gcd(3, 2) | 3 = 1 × 2 + 1 | 1 |
| gcd(2, 1) | 2 = 2 × 1 + 0 | 0 |
n = 0, so gcd(1, 0) = 1.
Part (iv)
| gcd(m, n) | m = q × n + r | r = m mod n |
|---|---|---|
| gcd(2587392, 157656) | 2587392 = 16 × 157656 + 64896 | 64896 |
| gcd(157656, 64896) | 157656 = 2 × 64896 + 27864 | 27864 |
| gcd(64896, 27864) | 64896 = 2 × 27864 + 9168 | 9168 |
| gcd(27864, 9168) | 27864 = 3 × 9168 + 360 | 360 |
| gcd(9168, 360) | 9168 = 25 × 360 + 168 | 168 |
| gcd(360, 168) | 360 = 2 × 168 + 24 | 24 |
| gcd(168, 24) | 168 = 7 × 24 + 0 | 0 |
n = 0, so gcd(24, 0) = 24.
(i) 75
(ii) 3000
(iii) 1
(iv) 24
Q2.
Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n.
Solution:
Let m ≥ n and divide m by n.
m = q × n + r
Here q is the quotient and r = m mod n.
Forward
d divides m and n ⇒ d divides n and r
Let m = ad and n = bd.
r = m − qn = ad − qbd = (a − qb)d
So d divides r. Also d divides n.
Converse
d divides n and r ⇒ d divides m
Let n = xd and r = yd.
m = qn + r = qxd + yd = (qx + y)d
So d divides m. Also d divides n.
Both directions hold.
d divides m and n if and only if d divides n and m mod n.
Q3.
Write an algorithm prime(n) to check if n is prime. (Hint: A prime number p has exactly two distinct factors, 1 and p. Can you make use of divisors(n) to write out prime(n)?)
Solution:
Algorithm
1. Compute the list divisors(n).
2. If the list has exactly two elements, report n is prime.
3. Otherwise, report n is not prime.
Examples
divisors(7) = [1, 7]. Two elements, so prime.
divisors(12) = [1, 2, 3, 4, 6, 12]. Six elements, so not prime.
divisors(1) = [1]. One element, so not prime.
n is prime exactly when divisors(n) has two elements.
Q4.
Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers.
(Hint: Compute divisors(n) and then filter out the primes in this list.)
Solution:
Algorithm
1. Compute the list divisors(n).
2. Start with an empty list prime-divisors.
3. For each x in divisors(n): if prime(x) is true, add x to prime-divisors.
4. Report prime-divisors.
Example
primedivisors(30) = [2, 3, 5]
primedivisors(18) = [2, 3]
Keep only those divisors x for which prime(x) holds.
Q5.
We can also find the gcd of two numbers by computing prime factorisation of both the numbers. Try to write an algorithm to compute the prime factorisation of a number.
(i) The prime factorisation of 180 is 22 × 32 × 51. How would you represent this?
(ii) How would you compare the prime factorisations of two numbers?
Solution:
Algorithm
1. Start with an empty list factors. Let rest = n.
2. For each p in primedivisors(n), in increasing order:
Set count = 0.
While p divides rest: divide rest by p and add 1 to count.
Add the pair (p, count) to factors.
3. Report factors.
| p | rest changes | count |
|---|---|---|
| 2 | 180 → 90 → 45 | 2 |
| 3 | 45 → 15 → 5 | 2 |
| 5 | 5 → 1 | 1 |
Part (i)
180 = 22 × 32 × 51
Represent it as a list of pairs (prime, power):
[(2, 2), (3, 2), (5, 1)]
Part (ii)
Compare the pairs prime by prime. Take 180 and 150.
180 = [(2, 2), (3, 2), (5, 1)]
150 = [(2, 1), (3, 1), (5, 2)]
For each prime, take the smaller power. Multiply.
gcd = 21 × 31 × 51 = 30
(i) Pairs (prime, power): [(2, 2), (3, 2), (5, 1)].
(ii) gcd takes the smaller power of each prime.
![When Will The New Class 9 Social Science [SST] NCERT be available Online](https://studyless.in/wp-content/uploads/2026/05/When-Will-The-New-Class-9-Social-Science-SST-NCERT-be-available-Online-1200x675.webp)
