Searching & SortingProblem 7 of 36
Find the repeating and the missing
Problem Statement
Given an unsorted array of size n containing numbers from 1 to n, one number is missing and one number appears twice. Find both the repeating and the missing numbers.
Constraints:
- Array contains n elements
- Elements are in range [1, n]
- Exactly one element is repeated
- Exactly one element is missing
Example:
- Input:
arr = [4, 3, 6, 2, 1, 1], n = 6 - Output:
Repeating = 1, Missing = 5 - Explanation: 1 appears twice, 5 is missing
Approach 1: Brute Force (Counting)
Intuition
Count occurrences of each number from 1 to n. The number with count 2 is repeating, and the one with count 0 is missing.
Algorithm
- For each number from 1 to n
- Count its occurrences in the array
- If count is 2, it's the repeating number
- If count is 0, it's the missing number
java
public class Solution {
public int[] findRepeatingMissing(int[] arr) {
int n = arr.length;
int repeating = -1, missing = -1;
for (int i = 1; i <= n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (arr[j] == i) {
count++;
}
}
if (count == 2) repeating = i;
if (count == 0) missing = i;
}
return new int[]{repeating, missing};
}
}Complexity Analysis
- Time Complexity: O(n²) - Nested loops
- Space Complexity: O(1) - No extra space
Approach 2: Using Count Array
Intuition
Use an auxiliary array to count occurrences of each element.
java
public class Solution {
public int[] findRepeatingMissing(int[] arr) {
int n = arr.length;
int[] count = new int[n + 1];
for (int num : arr) {
count[num]++;
}
int repeating = -1, missing = -1;
for (int i = 1; i <= n; i++) {
if (count[i] == 2) repeating = i;
if (count[i] == 0) missing = i;
}
return new int[]{repeating, missing};
}
}Complexity Analysis
- Time Complexity: O(n) - Two passes
- Space Complexity: O(n) - Count array
Approach 3: Mathematical Formulas (Optimal)
Intuition
Use mathematical equations to find the two unknowns.
Let x = repeating number, y = missing number
Equation 1: Sum difference
Sum(arr) - Sum(1 to n) = x - y
Let this be S
Equation 2: Sum of squares difference
Sum(arr²) - Sum(1² to n²) = x² - y² = (x+y)(x-y)
Let this be P
From these: x + y = P / S
Solving: x = (S + P/S) / 2 and y = x - S
Algorithm
- Calculate actual sum and sum of squares of array
- Calculate expected sum = n(n+1)/2 and expected sum of squares = n(n+1)(2n+1)/6
- Get difference S = actual_sum - expected_sum = x - y
- Get difference P = actual_sq_sum - expected_sq_sum = x² - y²
- Calculate x + y = P / S
- Solve for x and y
java
public class Solution {
public int[] findRepeatingMissing(int[] arr) {
long n = arr.length;
// Calculate actual sums
long actualSum = 0, actualSqSum = 0;
for (int num : arr) {
actualSum += num;
actualSqSum += (long) num * num;
}
// Calculate expected sums
long expectedSum = n * (n + 1) / 2;
long expectedSqSum = n * (n + 1) * (2 * n + 1) / 6;
// S = x - y
long S = actualSum - expectedSum;
// P = x² - y² = (x+y)(x-y) = (x+y) * S
long P = actualSqSum - expectedSqSum;
// x + y = P / S
long sumXY = P / S;
// x = (S + sumXY) / 2
int repeating = (int) ((S + sumXY) / 2);
int missing = (int) (sumXY - repeating);
return new int[]{repeating, missing};
}
}Dry Run Example
arr = [4, 3, 6, 2, 1, 1], n = 6
x = repeating, y = missing
actualSum = 4+3+6+2+1+1 = 17
actualSqSum = 16+9+36+4+1+1 = 67
expectedSum = 6*7/2 = 21
expectedSqSum = 6*7*13/6 = 91
S = 17 - 21 = -4 = x - y
P = 67 - 91 = -24 = x² - y²
x + y = P / S = -24 / -4 = 6
x - y = -4
x + y = 6
---------
2x = 2, x = 1 (repeating)
y = 6 - 1 = 5 (missing)
Result: Repeating = 1, Missing = 5 ✓
Complexity Analysis
- Time Complexity: O(n) - Single pass
- Space Complexity: O(1) - Only variables
Approach 4: XOR Method (Optimal)
Intuition
XOR all array elements with numbers 1 to n. The result is x XOR y. Then separate x and y using the rightmost set bit.
Algorithm
- XOR all elements in array with 1 to n → get x XOR y
- Find rightmost set bit in (x XOR y)
- Divide all numbers into two groups based on this bit
- XOR within each group to get x and y
- Determine which is repeating and which is missing
java
public class Solution {
public int[] findRepeatingMissingXOR(int[] arr) {
int n = arr.length;
// Step 1: XOR all elements with 1 to n
int xorAll = 0;
for (int i = 0; i < n; i++) {
xorAll ^= arr[i];
xorAll ^= (i + 1);
}
// Step 2: Find rightmost set bit
int rightmostBit = xorAll & (-xorAll);
// Step 3: Separate into two groups and XOR
int group1 = 0, group2 = 0;
for (int i = 0; i < n; i++) {
if ((arr[i] & rightmostBit) != 0) {
group1 ^= arr[i];
} else {
group2 ^= arr[i];
}
if (((i + 1) & rightmostBit) != 0) {
group1 ^= (i + 1);
} else {
group2 ^= (i + 1);
}
}
// Step 4: Determine which is repeating
for (int num : arr) {
if (num == group1) {
return new int[]{group1, group2};
}
}
return new int[]{group2, group1};
}
}Complexity Analysis
- Time Complexity: O(n) - Linear traversals
- Space Complexity: O(1) - Only variables
Approach 5: Index Marking (Modifying Array)
Intuition
Use the array indices as markers. Mark visited indices as negative. If we try to mark an already negative number, it's the repeating one.
Key Takeaways
- Mathematical Approach: Uses sum and sum of squares for O(n) time, O(1) space
- XOR Method: Elegant bit manipulation technique for O(n) time, O(1) space
- Index Marking: Uses array itself as hash map (modifies array)
- Two Equations: Need two independent equations to solve for two unknowns
- Overflow Handling: Use long/long long for sum calculations
- Rightmost Set Bit:
x & (-x)isolates the rightmost set bit