Summary of "Find the Missing and Repeating Number | 4 Approaches 🔥"

Summary of “Find the Missing and Repeating Number | 4 Approaches 🔥”

This video explains the problem of finding one missing and one repeating number in an array of size n containing numbers from 1 to n. It covers four approaches, starting from brute force to optimal solutions, emphasizing understanding, coding, and complexity analysis.

Problem Statement

Given an array of n integers where numbers range from 1 to n.
Exactly one number repeats twice (repeating number).
Exactly one number is missing (missing number).
Task: Return the repeating and missing numbers.

Approaches Covered

1. Brute Force Approach (Naive)

For each number from 1 to n:
- Iterate through the array and count occurrences.
- If count = 2 → repeating number.
- If count = 0 → missing number.
Time Complexity: O(n²) (two nested loops)
Space Complexity: O(1) (no extra space used)
Drawback: Inefficient for large inputs; interviewer usually expects better.

2. Better Solution Using Hashing (Frequency Array)

Create a hash/frequency array of size n+1, initialized to zero.
Iterate through the input array and increment count for each number.
Iterate from 1 to n:
- If frequency = 2 → repeating number.
- If frequency = 0 → missing number.
Time Complexity: O(n)
Space Complexity: O(n) (for hash array)
Drawback: Extra space usage; interviewer may ask for further optimization.

3. Optimal Mathematical Approach

Use mathematical formulas for sum and sum of squares of first n natural numbers:
- Sum of first n natural numbers: [ S_n = \frac{n(n+1)}{2} ]
- Sum of squares of first n natural numbers: [ S2_n = \frac{n(n+1)(2n+1)}{6} ]
Let ( x ) = repeating number, ( y ) = missing number.
Calculate:
- ( S = ) sum of array elements
- ( S2 = ) sum of squares of array elements
Form two equations:
- ( x - y = S - S_n ) (difference of sums)
- ( x^2 - y^2 = S2 - S2_n ) (difference of squares)
Use algebraic manipulation:
- ((x + y)(x - y) = x^2 - y^2)
- Hence, [ x + y = \frac{S2 - S2_n}{x - y} ]
Solve the two equations to get ( x ) and ( y ).
Time Complexity: O(n) (single pass to compute sums)
Space Complexity: O(1)
Note: Use 64-bit integers (e.g., long long) to avoid overflow.
This method is efficient and preferred in interviews.

4. Optimal Bit Manipulation (XOR) Approach

Use XOR properties:
- XOR of two same numbers = 0
- XOR of a number with 0 = number itself
Steps:
1. XOR all elements in the array and numbers from 1 to n. Result = ( x \oplus y ) (XOR of missing and repeating).
2. Find a set bit (rightmost set bit) in ( x \oplus y ) to differentiate ( x ) and ( y ).
3. Divide elements and numbers into two groups based on this set bit.
4. XOR all elements in each group separately → results in two numbers (( x ) and ( y )).
5. Determine which is missing and which is repeating by checking frequency.
Time Complexity: O(n)
Space Complexity: O(1)
Note: This approach is more complex but very efficient.
Useful if you know bit manipulation well.

Additional Notes

The video encourages understanding the problem-solving mindset rather than memorizing solutions.
Coding demonstrations for each approach are included.
Emphasis on writing clean code and considering integer overflow.
Encourages practicing on pen and paper for clarity.
Recommends the mathematical approach as the best balance of simplicity and efficiency.
The XOR method is optional and more advanced.

Speakers / Sources

Primary Speaker: The video creator (likely a coding instructor associated with the “Strivers A to Z DSA course”).
No other speakers mentioned.

Summary Table

Approach Time Complexity Space Complexity Key Idea Notes Brute Force O(n²) O(1) Count occurrences for each number Inefficient Hashing (Frequency) O(n) O(n) Use frequency array Extra space Mathematical (Sum + Sq) O(n) O(1) Use sum and sum of squares formulas Optimal, recommended Bit Manipulation (XOR) O(n) O(1) Use XOR and bit partitioning Advanced, optional

This comprehensive explanation helps learners understand various strategies to solve the missing and repeating number problem, their trade-offs, and implementation details.