Arrays: Find the Missing and Repeating Number (4 Comprehensive Approaches)

Given an array of $N$ integers where each element is supposed to be in the range $[1, N]$, exactly one integer appears twice (the Repeating Number $X$) and one integer is completely omitted (the Missing Number $Y$). The goal is to identify both $X$ and $Y$ and return them in the specific format [Repeating, Missing].

1. Problem Statement & Conceptual Grounding

Input Constraints & Characteristics

• An array arr of size $N$.
• The array contains values that should ideally represent all numbers from $1$ to $N$.
• Repeating Number ($X$): Appears $2$ times in the array.
• Missing Number ($Y$): Appears $0$ times in the array.
• All other numbers appear exactly $1$ time.

Concrete Example Walkthrough

Consider $N = 6$ and the input array: arr = [4, 3, 6, 2, 1, 1]

Comparing the given array against the expected set of numbers from $1$ to $6$:

Expected Numbers : 1, 2, 3, 4, 5, 6
Actual Array     : 4, 3, 6, 2, 1, 1

• Count of 1: $2$ times $\rightarrow$ Repeating Number ($X = 1$)
• Count of 2: $1$ time
• Count of 3: $1$ time
• Count of 4: $1$ time
• Count of 5: $0$ times $\rightarrow$ Missing Number ($Y = 5$)
• Count of 6: $1$ time

Target Output: [1, 5]

2. Core Mental Model & Solution Evolution

To solve this problem efficiently in technical interviews, you start with the most intuitive naive solution and progressively optimize both time and space complexity:

3. Approach 1: Brute Force ($O(N^2)$ Time, $O(1)$ Space)

Method Intuition

Iterate through every candidate integer $i$ from $1$ to $N$. For each integer $i$, traverse the entire array to count how many times it appears.

• If count == 2, then $i$ is the repeating number ($X$).
• If count == 0, then $i$ is the missing number ($Y$).

Code Implementation (C++)

#include <vector>
using namespace std;

vector<int> findMissingRepeatingBruteForce(vector<int>& arr) {
    int n = arr.size();
    int repeating = -1, missing = -1;

    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] == i) {
                cnt++;
            }
        }

        if (cnt == 2) repeating = i;
        else if (cnt == 0) missing = i;

        // Early exit if both numbers are found
        if (repeating != -1 && missing != -1) break;
    }

    return {repeating, missing};
}

Complexity Analysis

• Time Complexity: $O(N^2)$ — For each number from $1$ to $N$, we iterate through the array of size $N$.
• Space Complexity: $O(1)$ — Only auxiliary variables (repeating, missing, cnt) are used.

4. Approach 2: Better Strategy using Hashing ($O(N)$ Time, $O(N)$ Space)

Method Intuition

Instead of scanning the array repeatedly to count occurrences, we can use a frequency/hash array of size $N + 1$ initialized to $0$.

1. Perform a single pass over arr to populate the hash array: hash[arr[i]]++.
2. Perform a second pass over indices $1$ to $N$ in the hash array:
   • Index with value 2 is $X$ (Repeating).
   • Index with value 0 is $Y$ (Missing).

Frequency Tracking Flow

Code Implementation (C++)

#include <vector>
using namespace std;

vector<int> findMissingRepeatingHashing(vector<int>& arr) {
    int n = arr.size();
    vector<int> hash(n + 1, 0);

    // Step 1: Pre-fill frequency array
    for (int i = 0; i < n; i++) {
        hash[arr[i]]++;
    }

    int repeating = -1, missing = -1;

    // Step 2: Identify missing and repeating elements
    for (int i = 1; i <= n; i++) {
        if (hash[i] == 2) repeating = i;
        else if (hash[i] == 0) missing = i;

        if (repeating != -1 && missing != -1) break;
    }

    return {repeating, missing};
}

Complexity Analysis

• Time Complexity: $O(2N) = O(N)$ — One pass to count frequencies and one pass to scan the hash array.
• Space Complexity: $O(N)$ — Requires an extra array of size $N + 1$.

5. Approach 3: Optimal Strategy 1 — Mathematical Equations ($O(N)$ Time, $O(1)$ Space)

Method Intuition

To eliminate the $O(N)$ auxiliary space, we construct two algebraic equations with two variables:

• Let $X$ = Repeating Number
• Let $Y$ = Missing Number

We use the sum of natural numbers and sum of squares of natural numbers to build a system of linear equations.

Mathematical Formulation

Equation 1: Sum Difference ($X - Y$)

• Sum of array elements: $S = \sum_{i=0}^{N-1} \text{arr}[i]$
• Sum of first $N$ natural numbers: $S_N = \frac{N(N + 1)}{2}$

Equation 2: Sum of Squares Difference ($X^2 - Y^2$)

• Sum of squares of array elements: $S_2 = \sum_{i=0}^{N-1} \text{arr}[i]^2$
• Sum of squares of first $N$ natural numbers: $S_{2N} = \frac{N(N + 1)(2N + 1)}{6}$

Since $X - Y = \text{Val}_1$, we can derive $(X + Y)$:

Solving for $X$ and $Y$

Now we have two simple equations:

1. $X - Y = \text{Val}_1$
2. $X + Y = \text{Val}_2$

Adding equation (1) and equation (2):

Substituting $X$ back into equation (1):

Important Real-World Pitfall: When working with values where $N \approx 10^5$, $S_2$ and $S_{2N}$ will exceed standard 32-bit integer boundaries ($2 \times 10^9$). Always use 64-bit integers (long long in C++ / long in Java) to prevent overflow during calculations.

6. Step-by-Step Mathematical Walkthrough

Trace with Example: arr = [4, 3, 6, 2, 1, 1], $N = 6$

1. Calculate $S_N$ and $S$:

   • $S_N = \frac{6 \times 7}{2} = 21$
   • $S = 4 + 3 + 6 + 2 + 1 + 1 = 17$
   • $\text{Val}_1 = S - S_N = 17 - 21 = -4 \quad \implies \quad X - Y = -4$

2. Calculate $S_{2N}$ and $S_2$:

   • $S_{2N} = \frac{6 \times 7 \times 13}{6} = 91$
   • $S_2 = 4^2 + 3^2 + 6^2 + 2^2 + 1^2 + 1^2 = 16 + 9 + 36 + 4 + 1 + 1 = 67$
   • $S_2 - S_{2N} = 67 - 91 = -24 \quad \implies \quad X^2 - Y^2 = -24$

3. Solve for $\text{Val}_2$ ($X + Y$):

   • $\text{Val}_2 = \frac{X^2 - Y^2}{X - Y} = \frac{-24}{-4} = 6 \quad \implies \quad X + Y = 6$

4. Solve for $X$ and $Y$:

   • $X = \frac{\text{Val}_1 + \text{Val}_2}{2} = \frac{-4 + 6}{2} = \frac{2}{2} = 1$
   • $Y = X - \text{Val}_1 = 1 - (-4) = 5$

Result: $X = 1$ (Repeating), $Y = 5$ (Missing).

Code Implementation (C++)

#include <vector>
using namespace std;

vector<int> findMissingRepeatingMath(vector<int>& arr) {
    long long n = arr.size();

    // Sum of N numbers and N^2 numbers
    long long SN = (n * (n + 1)) / 2;
    long long S2N = (n * (n + 1) * (2 * n + 1)) / 6;

    // Calculate actual array sums
    long long S = 0, S2 = 0;
    for (int i = 0; i < n; i++) {
        S += arr[i];
        S2 += (long long)arr[i] * (long long)arr[i];
    }

    // Val1 = X - Y
    long long val1 = S - SN;

    // Val2 = X + Y
    long long val2 = (S2 - S2N) / val1;

    // Calculate X and Y
    long long x = (val1 + val2) / 2;
    long long y = x - val1;

    return {(int)x, (int)y};
}

Complexity Analysis

• Time Complexity: $O(N)$ — Single iteration over the array to compute $S$ and $S_2$.
• Space Complexity: $O(1)$ — Constant extra memory used.

7. Approach 4: Optimal Strategy 2 — Bit Manipulation / XOR ($O(N)$ Time, $O(1)$ Space)

Core XOR Properties

1. $A \oplus A = 0$ (Self-cancellation)
2. $A \oplus 0 = A$ (Identity)
3. Commutative and Associative: Order of XOR operations does not matter.

Conceptual Mechanics

1. Calculate Global XOR: XOR all elements in arr together with all numbers from $1$ to $N$:

Because every standard number appears twice (once in arr and once in $1..N$), they cancel out to $0$.

• $X$ appears 3 times (2 in array + 1 in range) $\rightarrow$ leaves $X$.
• $Y$ appears 1 time (0 in array + 1 in range) $\rightarrow$ leaves $Y$.

2. Identify Differentiating Bit: Since $X \neq Y$, $X \oplus Y$ must have at least one set bit (1). A set bit at position $k$ implies that $X$ and $Y$ have differentiating bits at index $k$ (one has 0, the other has 1).

3. Bucket Categorization ("Zero-Club" vs. "One-Club"): Partition all array elements and numbers $1 \dots N$ into two groups based on whether their $k$-th bit is 0 or 1:

   • Zero-Bucket: All numbers with bit $k = 0$.
   • One-Bucket: All numbers with bit $k = 1$.

   XORing all elements inside the Zero-Bucket isolates one target number, and XORing all elements in the One-Bucket isolates the other!

4. Identify Which is Missing and Which is Repeating: After obtaining two isolated numbers $A$ and $B$, make a quick pass through arr to count occurrences of $A$:

   • If $A$ appears twice in arr $\rightarrow X = A$ (Repeating) and $Y = B$ (Missing).
   • Otherwise $\rightarrow X = B$ (Repeating) and $Y = A$ (Missing).

8. XOR Bucket Partition Walkthrough

Example Walkthrough: arr = [4, 3, 6, 2, 1, 1], $N = 6$

Array Elements : 4, 3, 6, 2, 1, 1
Range Elements : 1, 2, 3, 4, 5, 6

XR = (4 ^ 3 ^ 6 ^ 2 ^ 1 ^ 1) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6)
XR = 1 ^ 5 = (001)_2 ^ (101)_2 = (100)_2 = 4

• Position of set bit: Bit Index 2 (value 4 in binary 100).

Categorization into Buckets based on Bit Index 2

XOR Bucket Accumulation

• Zero-Bucket XOR: $(3 \oplus 2 \oplus 1 \oplus 1) \oplus (1 \oplus 2 \oplus 3) = 1$
• One-Bucket XOR: $(4 \oplus 6) \oplus (4 \oplus 5 \oplus 6) = 5$

Candidate values obtained: $1$ and $5$.

Final Verification Pass

Traverse arr to count occurrences of $1$:

• $1$ appears $2$ times in arr.
• Therefore: Repeating ($X$) = 1, Missing ($Y$) = 5.

9. Complete C++ Implementation of Both Optimal Approaches

Code 1: Mathematical Solution

#include <iostream>
#include <vector>

using namespace std;

vector<int> findMissingRepeatingMath(const vector<int>& a) {
    long long n = a.size();
    
    long long SN = (n * (n + 1)) / 2;
    long long S2N = (n * (n + 1) * (2 * n + 1)) / 6;
    
    long long S = 0, S2 = 0;
    for (int i = 0; i < n; i++) {
        S += a[i];
        S2 += (long long)a[i] * (long long)a[i];
    }
    
    long long val1 = S - SN; // X - Y
    long long val2 = (S2 - S2N) / val1; // X + Y
    
    long long x = (val1 + val2) / 2;
    long long y = x - val1;
    
    return {(int)x, (int)y};
}

Code 2: XOR Bit Manipulation Solution

#include <iostream>
#include <vector>

using namespace std;

vector<int> findMissingRepeatingXOR(const vector<int>& a) {
    int n = a.size();
    int xr = 0;

    // Step 1: XOR all array elements and range elements 1..N
    for (int i = 0; i < n; i++) {
        xr ^= a[i];
        xr ^= (i + 1);
    }

    // Step 2: Find differentiating bit (rightmost set bit)
    // Bitwise trick: (xr & ~(xr - 1)) isolates the rightmost set bit
    int bitNo = 0;
    while (true) {
        if ((xr & (1 << bitNo)) != 0) {
            break;
        }
        bitNo++;
    }

    // Step 3: Group numbers into Zero-Bucket and One-Bucket
    int zero = 0;
    int one = 0;

    // Separate array elements
    for (int i = 0; i < n; i++) {
        if ((a[i] & (1 << bitNo)) != 0) {
            one ^= a[i];
        } else {
            zero ^= a[i];
        }
    }

    // Separate range 1..N elements
    for (int i = 1; i <= n; i++) {
        if ((i & (1 << bitNo)) != 0) {
            one ^= i;
        } else {
            zero ^= i;
        }
    }

    // Step 4: Cross-check to confirm repeating and missing numbers
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == zero) cnt++;
    }

    if (cnt == 2) {
        return {zero, one}; // zero is repeating, one is missing
    }
    return {one, zero};     // one is repeating, zero is missing
}

10. Complexity Matrix & Trade-off Analysis

11. Summary and Key Takeaways

1. Problem Definition: Find one repeating integer $X$ (count = 2) and one missing integer $Y$ (count = 0) from an un-sorted array of size $N$ containing elements from $1$ to $N$.
2. Brute Force Baseline: Counting frequencies using nested loops yields an $O(N^2)$ time and $O(1)$ space complexity, which is impractical for large inputs ($N > 10^4$).
3. Space-Time Trade-off (Hashing): Storing counts in an auxiliary array of size $N + 1$ reduces time complexity to $O(N)$, but introduces $O(N)$ auxiliary space overhead.
4. Optimal Math Solution: Uses the difference of actual sums vs. expected sums ($S - S_N = X - Y$) combined with actual sum of squares vs. expected sum of squares ($S_2 - S_{2N} = X^2 - Y^2$) to build solvable linear equations in $O(N)$ time and $O(1)$ space.
5. Critical Pitfall in Math Approach: Calculating sum of squares ($S_2$) for $N \approx 10^5$ causes standard 32-bit integer overflow. Data structures must be Typecast to 64-bit integers (long long).
6. Optimal Bit Manipulation Solution: XORing all array values with numbers $1 \dots N$ eliminates paired identical values, resulting in $\text{XR} = X \oplus Y$.
7. Differentiating Bit Concept: Because $X \neq Y$, $X \oplus Y$ contains at least one set bit (1). Partitioning elements based on this bit isolates $X$ and $Y$ into separate buckets.
8. Overflow Safety: The XOR method processes bits directly without accumulating massive sum totals, completely eliminating integer overflow risks in any language.
9. Final Verification Step: Both mathematical and bit manipulation approaches compute two unique candidate values. A single $O(N)$ linear check is required to definitively assign which candidate is repeating and which is missing.