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

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.

UNDERSTAND THE QUESTION

  • The question asks us to describe procedures (algorithms) using step-by-step logical instructions to compare two ordered lists of numbers, L1L_1 and L2L_2.
  • Part (i) requires finding elements present in L1L_1 that are not in L2L_2.
  • Part (ii) requires finding elements present in L2L_2 that are not in L1L_1.
  • In Class 9 mathematics, systematic listing, logical deduction, and comparison of collections of numbers form part of basic number operations and reasoning.

(i)PART I

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

Step 1 — INITIALIZATION

Given two lists of numbers L1L_1 and L2L_2, both arranged in increasing order. Initialize two pointers or indices, say i=1i = 1 for list L1L_1 and j=1j = 1 for list L2L_2, and create an empty result list RR to store the required elements.

Step 2 — COMPARISON LOOP

Repeat the following steps while ii is within the length of L1L_1 and jj is within the length of L2L_2:

1. Compare the elements L1[i] and L2[j].2. If L1[i]<L2[j], it means L1[i] is smaller than any remaining element in L2 (since L2 is in increasing order). Therefore, L1[i] is not in L2. Add L1[i] to result list R and increase i by 1.3. If L1[i]=L2[j], the element exists in both lists. Increase both i and j by 1.4. If L1[i]>L2[j], the element in L2 is smaller. Increase j by 1 to check the next element in L2.\begin{aligned} \text{1. Compare the elements } L_1[i] \text{ and } L_2[j]. \\[0.6em] \text{2. If } L_1[i] < L_2[j]\text{, it means } L_1[i] \text{ is smaller than any remaining element in } L_2 \text{ (since } L_2 \text{ is in increasing order). Therefore, } L_1[i] \text{ is not in } L_2\text{. Add } L_1[i] \text{ to result list } R \text{ and increase } i \text{ by } 1. \\[0.6em] \text{3. If } L_1[i] = L_2[j]\text{, the element exists in both lists. Increase both } i \text{ and } j \text{ by } 1. \\[0.6em] \text{4. If } L_1[i] > L_2[j]\text{, the element in } L_2 \text{ is smaller. Increase } j \text{ by } 1 \text{ to check the next element in } L_2. \end{aligned}

Step 3 — HANDLING REMAINING ELEMENTS

If there are still elements left in L1L_1 after the end of list L2L_2 is reached (i.e., jj exceeds the length of L2L_2), all remaining elements in L1L_1 are greater than all elements in L2L_2 and thus cannot be present in L2L_2. Add all remaining elements of L1L_1 to the result list RR.

ANSWER (I)

The result list RR contains all elements of L1L_1 that are not present in L2L_2.

(ii)PART II

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

Step 1 — INITIALIZATION

Given two lists of numbers L1L_1 and L2L_2, both arranged in increasing order. Initialize pointers i=1i = 1 for list L1L_1 and j=1j = 1 for list L2L_2, and create an empty result list RR.

Step 2 — COMPARISON LOOP

Repeat the following steps while ii is within the length of L1L_1 and jj is within the length of L2L_2:

1. Compare the elements L1[i] and L2[j].2. If L2[j]<L1[i], it means L2[j] is smaller than any remaining element in L1 (since L1 is in increasing order). Therefore, L2[j] is not in L1. Add L2[j] to result list R and increase j by 1.3. If L2[j]=L1[i], the element exists in both lists. Increase both i and j by 1.4. If L2[j]>L1[i], the element in L1 is smaller. Increase i by 1 to check the next element in L1.\begin{aligned} \text{1. Compare the elements } L_1[i] \text{ and } L_2[j]. \\[0.6em] \text{2. If } L_2[j] < L_1[i]\text{, it means } L_2[j] \text{ is smaller than any remaining element in } L_1 \text{ (since } L_1 \text{ is in increasing order). Therefore, } L_2[j] \text{ is not in } L_1\text{. Add } L_2[j] \text{ to result list } R \text{ and increase } j \text{ by } 1. \\[0.6em] \text{3. If } L_2[j] = L_1[i]\text{, the element exists in both lists. Increase both } i \text{ and } j \text{ by } 1. \\[0.6em] \text{4. If } L_2[j] > L_1[i]\text{, the element in } L_1 \text{ is smaller. Increase } i \text{ by } 1 \text{ to check the next element in } L_1. \end{aligned}

Step 3 — HANDLING REMAINING ELEMENTS

If there are still elements left in L2L_2 after the end of list L1L_1 is reached (i.e., ii exceeds the length of L1L_1), all remaining elements in L2L_2 are greater than all elements in L1L_1 and thus cannot be present in L1L_1. Add all remaining elements of L2L_2 to the result list RR.

ANSWER (II)

The result list RR contains all elements of L2L_2 that are not present in L1L_1.

COMMON MISTAKES

  • Ignoring the Sorted Property: Searching through the entire second list for every element without utilizing the fact that both lists are already arranged in increasing order.
  • Boundary Errors: Forgetting to handle the case where one list ends before the other.

Was this solution helpful?

Quick Concept Check: Test Your Understanding

Interactive self-testing widget

?
If two lists L1L_1 and L2L_2 are given in increasing order, and during comparison L1[i]<L2[j]L_1[i] < L_2[j], what does it imply?