If you’re preparing for coding interviews, the “Missing And Repeating” problem is a classic! In this blog, we’ll explain the problem, walk you through brute force, better, and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.
Given an unsorted array arr of positive integers. One number a from the set [1, 2,….,n] is missing and one number b occurs twice in the array. Find numbers a and b.
Note: The test cases are generated such that there always exists one missing and one repeating number within the range [1,n].
Here’s the [Problem Link] to begin with.
Examples:
Input: arr[] = [2, 2]
Output: [2, 1]
Explanation: Repeating number is 2 and smallest positive missing number is 1.
Input: arr[] = [1, 3, 3] Output: [3, 2] Explanation: Repeating number is 3 and smallest positive missing number is 2.
Input: arr[] = [4, 3, 6, 2, 1, 1]
Output: [1, 5]
Explanation: Repeating number is 1 and the missing number is 5.
Constraints:
2 ≤ arr.size() ≤ 106
1 ≤ arr[i] ≤ arr.size()
Brute Force Solution (Nested Loops)
Intuition and Approach
Let’s solve the problem in the simplest way:
- Count Occurrences:
For each number from 1 to n, count how many times it appears in the array. - Identify Repeating and Missing:
- If a number appears twice, it’s the repeating number.
- If a number doesn’t appear at all, it’s the missing number.
- Why does this work?
We check every number, so we’re sure to find both the missing and repeating numbers.
This approach is easy to understand but not efficient for large arrays.
Code Implementation
class Solution:
def findTwoElement(self, arr):
n = len(arr)
repeating, missing = -1, -1
for i in range(1, n + 1):
count = 0
for j in range(n):
if arr[j] == i:
count += 1
if count == 2:
repeating = i
elif count == 0:
missing = i
if repeating != -1 and missing != -1:
break
return [repeating, missing]
PythonCode Explanation
- For each number from 1 to n, we count how many times it appears in the array.
- If a number appears twice, we store it as
repeating
. - If a number doesn’t appear at all, we store it as
missing
. - As soon as we find both, we return the answer.
Dry Run
Input:arr = [1][1]
- Check 1: appears 2 times → repeating = 1
- Check 2: appears 1 time
- Check 3: appears 1 time
- Check 4: appears 1 time
- Check 5: appears 0 times → missing = 5
- Check 6: appears 1 time
Output:[1]
Time and Space Complexity
- Time Complexity: O(n^2)
Two nested loops: for each number, check the whole array. - Space Complexity: O(1)
Only a few variables are used.
Conclusion
The brute force approach is simple and good for understanding, but it’s too slow for large arrays.
Better Solution (Hashing)
Intuition and Approach
Let’s make it faster using extra space:
- Create a Hash Array:
Make an array to count how many times each number appears. - Scan for Repeating and Missing:
- If a number appears twice, it’s the repeating number.
- If a number doesn’t appear, it’s the missing number.
- Why does this work?
Counting with a hash array is much faster than nested loops.
Code Implementation
class Solution:
def findTwoElement(self, arr):
n = len(arr)
repeating, missing = -1, -1
hash_list = [0] * (n + 1) # create a hash list to count occurrences
for num in arr:
hash_list[num] += 1 # count each number
for i in range(1, len(hash_list)):
if hash_list[i] == 2: # found repeating number
repeating = i
elif hash_list[i] == 0: # found missing number
missing = i
if repeating != -1 and missing != -1:
return [repeating, missing]
PythonCode Explanation
- We use a hash array to count how many times each number appears.
- If a number appears twice, it’s repeating.
- If a number doesn’t appear, it’s missing.
- As soon as we find both, we return the answer.
Dry Run
Input:arr = [1][1]
- hash_list after counting:
[1][1][1][1]
- 1 appears 2 times → repeating = 1
- 5 appears 0 times → missing = 5
Output:[1]
Time and Space Complexity
- Time Complexity: O(n)
One pass to count, one pass to check. - Space Complexity: O(n)
Extra space for the hash array.
Conclusion
The better solution is much faster and is a good choice for medium-sized arrays.
Optimal Solution (Maths: Sum and Sum of Squares)
Intuition and Approach
Let’s solve the problem with no extra space and in just one pass:
- Maths Approach:
- Let the missing number be
y
and the repeating number bex
. - Calculate the sum and sum of squares of the first n natural numbers.
- Calculate the sum and sum of squares of the array.
- Use these two equations:
x - y = sum(arr) - sum(1...n)
x^2 - y^2 = sum_of_squares(arr) - sum_of_squares(1...n)
- Let the missing number be
- Solve the Equations:
- From above, calculate
x + y
and then findx
andy
.
- From above, calculate
- Why does this work?
The difference in sums and squares gives us two equations to solve for the missing and repeating numbers.
Code Implementation
class Solution:
def findTwoElement(self, arr):
n = len(arr)
sN = (n * (n + 1)) // 2 # sum of first n numbers
s2N = (n * (n + 1) * (2 * n + 1)) // 6 # sum of squares of first n numbers
s = 0
s2 = 0
for num in arr:
s += num # sum of array
s2 += num**2 # sum of squares of array
val1 = s - sN # x - y
val2 = s2 - s2N # x^2 - y^2
val2 = val2 // val1 # (x^2 - y^2) // (x - y) = x + y
x = (val1 + val2) // 2 # repeating number
y = x - val1 # missing number
return [x, y]
PythonCode Explanation
- Calculate expected sum and sum of squares for numbers 1 to n.
- Calculate actual sum and sum of squares for the given array.
- Use the differences to set up equations and solve for missing and repeating numbers.
Dry Run
Input:arr = [1][1]
- n = 6
- sN = 21, s2N = 91
- s = 17, s2 = 63
- val1 = s – sN = -4
- val2 = s2 – s2N = -28
- val2 // val1 = 7
- x = (val1 + val2) // 2 = (–4 + 7) // 2 = 1
- y = x – val1 = 1 – (–4) = 5
Output:[1]
Time and Space Complexity
- Time Complexity: O(n)
Only one pass for sums. - Space Complexity: O(1)
Only variables, no extra arrays.
Conclusion
The optimal solution is fast and uses no extra space. It’s the best approach for interviews and large datasets.
Final Thoughts
The “Missing And Repeating” problem is a great example of how to optimize your solution step by step. Start with brute force to understand the basics, then use hashing for speed, and finally use maths for the most efficient answer.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.