Find Two Missing Numbers | Set 1 (An Interesting Linear Time Solution)

Table of Contents#

1. Problem Statement
2. Naive Approach
3. The Linear - Time Solution
   • Understanding the Concept
   • Mathematical Formulas
   • Step - by - Step Algorithm
4. Implementation in Python
5. Complexity Analysis
6. Best Practices and Common Considerations
7. Example Usage
8. Conclusion
9. References

1. Problem Statement#

We are given an array of distinct integers from the range 1 to n, where two numbers are missing. The task is to find these two missing numbers in the most efficient way possible. For instance, if n = 5 and the given array is [1, 2, 4], then the two missing numbers are 3 and 5.

2. Naive Approach#

The simplest way to solve this problem is to first create a set of all numbers from 1 to n. Then, iterate through the given array and remove each element from the set. After the iteration, the remaining two elements in the set are the missing numbers.

def find_missing_naive(arr, n):
    full_set = set(range(1, n + 1))
    for num in arr:
        full_set.discard(num)
    return list(full_set)
 
 
arr = [1, 2, 4]
n = 5
print(find_missing_naive(arr, n))

This approach has a time complexity of $O(n)$ because we are iterating through the array once. However, it requires $O(n)$ extra space to store the set.

3. The Linear - Time Solution#

Understanding the Concept#

The key idea behind the linear - time solution is to use the properties of sums and sums of squares of the first n natural numbers. We know the formula for the sum of the first n natural numbers and the sum of their squares. By calculating the actual sum and sum of squares of the given array, we can find the sum and sum of squares of the two missing numbers. Then, using these values, we can solve a system of equations to find the two missing numbers.

Mathematical Formulas#

• The sum of the first n natural numbers is given by the formula: $S_n=\frac{n(n + 1)}{2}$
• The sum of the squares of the first n natural numbers is given by the formula: $S_{n^2}=\frac{n(n + 1)(2n + 1)}{6}$

Let the two missing numbers be $x$ and $y$.

• The actual sum of the given array is $S_{actual}$. Then $x + y=S_n - S_{actual}$
• The actual sum of squares of the given array is $S_{actual^2}$. Then $x^{2}+y^{2}=S_{n^2}-S_{actual^2}$

We also know that $(x + y)^2=x^{2}+2xy + y^{2}$. So, $xy=\frac{(x + y)^2-(x^{2}+y^{2})}{2}$

We can then solve the quadratic equation $t^2-(x + y)t+xy = 0$ to find the values of $x$ and $y$.

Step - by - Step Algorithm#

1. Calculate $S_n$ and $S_{n^2}$ using the above - mentioned formulas.
2. Calculate $S_{actual}$ and $S_{actual^2}$ by iterating through the given array.
3. Calculate $x + y$ and $x^{2}+y^{2}$.
4. Calculate $xy$.
5. Solve the quadratic equation $t^2-(x + y)t+xy = 0$ using the quadratic formula $t=\frac{(x + y)\pm\sqrt{(x + y)^2-4xy}}{2}$.

4. Implementation in Python#

import math
 
 
def find_two_missing_numbers(arr, n):
    # Calculate sum and sum of squares of first n natural numbers
    sum_n = n * (n + 1) // 2
    sum_n_sq = n * (n + 1) * (2 * n + 1) // 6
 
    # Calculate sum and sum of squares of given array elements
    sum_actual = 0
    sum_actual_sq = 0
    for num in arr:
        sum_actual += num
        sum_actual_sq += num * num
 
    # Calculate sum and sum of squares of two missing numbers
    sum_missing = sum_n - sum_actual
    sum_missing_sq = sum_n_sq - sum_actual_sq
 
    # Calculate product of two missing numbers
    product_missing = (sum_missing ** 2 - sum_missing_sq) // 2
 
    # Solve quadratic equation
    # t^2 - (sum_missing)t + product_missing = 0
    discriminant = sum_missing ** 2 - 4 * product_missing
    root1 = (sum_missing + math.sqrt(discriminant)) // 2
    root2 = (sum_missing - math.sqrt(discriminant)) // 2
 
    return [int(root1), int(root2)]
 
 
arr = [1, 2, 4]
n = 5
print(find_two_missing_numbers(arr, n))

5. Complexity Analysis#

• Time Complexity: The time complexity of this algorithm is $O(n)$ because we are iterating through the array only once to calculate the actual sum and sum of squares.
• Space Complexity: The space complexity is $O(1)$ because we are using only a constant amount of extra space.

6. Best Practices and Common Considerations#

• Precision: When dealing with square roots in the quadratic formula, be aware of potential precision issues in floating - point arithmetic. In Python, we can convert the final result to integers to avoid such issues.
• Error Handling: If the input array is not valid (e.g., contains non - distinct elements or elements out of the range 1 to n), handle the errors gracefully.

7. Example Usage#

Let's assume we have an array representing the scores of students in a class where the scores are supposed to be in the range 1 to 10, but two scores are missing.

arr = [1, 3, 4, 5, 7, 8, 9, 10]
n = 10
missing = find_two_missing_numbers(arr, n)
print(f"The two missing scores are {missing[0]} and {missing[1]}")

8. Conclusion#

The linear - time solution to find two missing numbers is an efficient way to solve the problem compared to the naive approach as it uses constant space. By leveraging mathematical properties, we can reduce the space complexity significantly without sacrificing the time complexity.

9. References#

• Python documentation: https://docs.python.org/
• Mathematical formulas reference: https://en.wikipedia.org/wiki/Sum_of_squares#Sum_of_the_squares_of_the_first_n_positive_integers
• Competitive Programming Handbook by Antti Laaksonen.