.png)
Find Repeating and Missing Numbers
Problem Statement
You are given an array arr of size n containing numbers from 1 to n.
- One number is repeating
- One number is missing
Your task is to find both numbers.
Example 1
Input
arr = [3, 1, 2, 5, 3]
Output
Repeating = 3
Missing = 4
Example 2
Input
arr = [1, 2, 2, 4]
Output
Repeating = 2
Missing = 3
Why This Problem Is Important
- Very common interview question
- Tests math, hashing, and bit manipulation
- Asked in Google, Amazon, Microsoft
- Foundation for array integrity problems
Approaches Overview
| No | Approach | Technique | Time | Space |
|---|---|---|---|---|
| 1 | Brute Force | Counting | O(n²) | O(1) |
| 2 | Hashing | Frequency array | O(n) | O(n) |
| 3 | Mathematical | Sum & Sum of Squares | O(n) | O(1) |
| 4 | XOR Method | Bit manipulation | O(n) | O(1) |
Approach 1: Brute Force
Idea
- For every number from 1 to n
- Count its frequency in the array
- Frequency 2 → Repeating
- Frequency 0 → Missing
Time and Space Complexity
- Time: O(n²)
- Space: O(1)
Python Implementation
def findMissingRepeating(arr):
n = len(arr)
repeating = missing = -1
for i in range(1, n+1):
count = 0
for num in arr:
if num == i:
count += 1
if count == 2:
repeating = i
elif count == 0:
missing = i
return repeating, missing
Output
(1, 5)C++ Implementation
#include
using namespace std;
pair findMissingRepeating(vector& arr){
int n = arr.size();
int repeating = -1, missing = -1;
for(int i=1;i<=n;i++){
int count = 0;
for(int num : arr)
if(num == i) count++;
if(count == 2) repeating = i;
else if(count == 0) missing = i;
}
return {repeating, missing};
}
Output
1 5Java Implementation
class Main {
static int[] findMissingRepeating(int[] arr){
int n = arr.length;
int repeating = -1, missing = -1;
for(int i=1;i<=n;i++){
int count = 0;
for(int num : arr)
if(num == i) count++;
if(count == 2) repeating = i;
else if(count == 0) missing = i;
}
return new int[]{repeating, missing};
}
}
Output
1 5JavaScript Implementation
function findMissingRepeating(arr){
let n = arr.length;
let repeating = -1, missing = -1;
for(let i=1;i<=n;i++){
let count = 0;
for(let num of arr)
if(num === i) count++;
if(count === 2) repeating = i;
else if(count === 0) missing = i;
}
return [repeating, missing];
}
Output
(1, 5)C# Implementation
static (int,int) FindMissingRepeating(int[] arr){
int n = arr.Length;
int repeating = -1, missing = -1;
for(int i=1;i<=n;i++){
int count = 0;
foreach(int num in arr)
if(num == i) count++;
if(count == 2) repeating = i;
else if(count == 0) missing = i;
}
return (repeating, missing);
}
Output
1 5Approach 2: Hashing
Idea
- Use frequency array of size n+1
- Track occurrences
- Missing → frequency 0
- Repeating → frequency 2
Time and Space Complexity
- Time: O(n)
- Space: O(n)
Python Implementation
def findMissingRepeating(arr):
n = len(arr)
freq = [0]*(n+1)
for num in arr:
freq[num] += 1
for i in range(1, n+1):
if freq[i] == 0:
missing = i
elif freq[i] == 2:
repeating = i
return repeating, missing
Output
(1, 5)C++ Implementation
pair findMissingRepeating(vector& arr){
int n = arr.size();
vector freq(n+1, 0);
for(int num : arr) freq[num]++;
int repeating, missing;
for(int i=1;i<=n;i++){
if(freq[i] == 0) missing = i;
else if(freq[i] == 2) repeating = i;
}
return {repeating, missing};
}
Output
1 5Java Implementation
class Main {
static int[] findMissingRepeating(int[] arr){
int n = arr.length;
int[] freq = new int[n+1];
for(int num : arr) freq[num]++;
int repeating = -1, missing = -1;
for(int i=1;i<=n;i++){
if(freq[i] == 0) missing = i;
else if(freq[i] == 2) repeating = i;
}
return new int[]{repeating, missing};
}
}
Output
1 5JavaScript Implementation
function findMissingRepeating(arr){
let n = arr.length;
let freq = Array(n+1).fill(0);
for(let num of arr) freq[num]++;
let repeating, missing;
for(let i=1;i<=n;i++){
if(freq[i] === 0) missing = i;
else if(freq[i] === 2) repeating = i;
}
return [repeating, missing];
}
Output
(1, 5)C# Implementation
static (int,int) FindMissingRepeating(int[] arr){
int n = arr.Length;
int[] freq = new int[n+1];
foreach(int num in arr) freq[num]++;
int repeating = -1, missing = -1;
for(int i=1;i<=n;i++){
if(freq[i] == 0) missing = i;
else if(freq[i] == 2) repeating = i;
}
return (repeating, missing);
}Output
1 5Final Summary
| Approach | Best Use Case |
|---|---|
| Brute Force | Concept clarity |
| Hashing | Simple and safe |
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
