DSA

Missing and Repeating Number

4 approaches incl. Brute Force, Better, Maths, and more. Optimal — Time O(n), Space O(1).

August 8, 2026

DSA Intervals Arrays LeetCode Practice

Brute Force Approach#

Sort the array and scan.

Intuition: In a sorted array of numbers 1 to n with one number duplicated and one missing, the missing number creates a gap (two consecutive elements differ by 2) and the repeating number appears twice in a row.
Mechanics: Sort the array in O(n log n), then do a single linear pass comparing each element to its expected value (i+1) to detect both anomalies.
Trade-off: Simple to implement with no extra space, but O(n log n) time is worse than the O(n) hashing, math, and XOR approaches. Also modifies the input array unless a copy is made.

Time Complexity: O(n log n)

Space Complexity: O(1)

Better Approach#

Intuition: Count occurrences of every number using a hash array. Any number with count 2 is the repeating one; any number with count 0 is the missing one.
Mechanics: Allocate a frequency array of size n+1 initialised to 0. One pass over the input marks the repeating number when its hash cell is already non-zero. A second pass over the hash array finds the zero-count index, which is the missing number.
Trade-off: Reduces time from O(n log n) to O(n) with two linear passes. The downside is O(n) extra space for the hash array, which is eliminated by the math and XOR approaches.

cpp

class Solution {
public:
    vector<int> findMissingRepeatingNumbers(vector<int> nums) {
        vector<int> hash(nums.size()+1, 0);

        int missing=-1, repeating;
        for(int i=0;i<nums.size();i++)
        {
            if(hash[nums[i]]!= 0)
                repeating=nums[i];
            hash[nums[i]]++;
        }

        for(int i=0;i<hash.size();i++)
            if(hash[i]==0)
                missing = i;

        return {repeating, missing};
    }
};

Time Complexity: O(n) -> Two traversal

Space Complexity: O(n)

Maths Approach#

Expected Sum and Sum of Squares
- Sum of first n numbers:
```
Sn = n * (n + 1) / 2
```
- Sum of squares of first n numbers:
```
Sn2 = n * (n + 1) * (2n + 1) / 6
```

Compute Differences

Let:

S  = sum of array elements
S2 = sum of squares of array elements

Then:
```
x - y = S  - Sn
x² - y² = S2 - Sn2
```

Form Linear Equations

Use the identity:
```
x² - y² = (x - y) * (x + y)
```
Compute:
```
x + y = (x² - y²) / (x - y)
```

Solve for x and y

Implementation#

cpp

class Solution {
public:
    vector<int> solveTwoLinearEquations(int diff, int sum)
    {
        // y = (x+y)/(2*(x-y));
        long long y = (sum-diff)/2;
        long long x = diff+y;
        return {(int)x,(int)y};
    }

    vector<int> findMissingRepeatingNumbers(vector<int> nums) {

        // assume 
        // x->repeating number
        // y->missing number
        int n = nums.size();

        // equation 1: S - Sn = x - y
        // equation 2: (S)^2 - (Sn)^2 = (x)2 - (y)2
        long long Sn = 1LL * n * (n+1)/2;
        long long Sn2 = 1LL * n * (n+1) * ((2*n)+1)/6;

        long long S = 0;
        long long S2 = 0;
        for(int num: nums){
            S += num;
            S2 += 1LL * num*num;
        }

        
        long long x_minus_y = S - Sn; //x - y
        long long x2_minus_y2 = S2 - Sn2; // x^2 - y^2
        long long x_plus_y = x2_minus_y2 / x_minus_y; //x + y

        return solveTwoLinearEquations(x_minus_y, x_plus_y); 

    }
};

Time Complexity: O(n)

Space Complexity: O(1)

XOR approach#

XOR cancel duplicates because

x ^ x = 0
x ^ 0 = x

If we XOR all elements of the array and all numbers from 1 to n, all pairs will cancel out, leaving: xr = Missing ^ Repeating
Since the two numbers are different, there will be at least one bit where they differ.
- Use that rightmost set bit to separate the numbers into two groups.
- Each group contains numbers contributing to either missing or repeating.
After XORing separately, we get two candidates → determine which one is repeating by checking array.

cpp

class Solution {
public:
    vector<int> findMissingRepeatingNumbers(vector<int> nums) {

        //find XOR(all ele of nums and all numbers 1 to n)
        int xr = 0;
        for(int i=0;i<nums.size();i++)
        {
            xr ^= nums[i];
            xr ^= i+1;
        }

        // find rightmost differentiating bit
        int bitNo = 0;
        while(1){
            if((xr & (1&lt;&lt; bitNo)) != 0)
                break;
            bitNo++;
        }

        //seperate all ele and numbers 1 to n into group of zero and one based on the bitNo
        int one =0;
        int zero=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i] & (1&lt;<bitNo))
                one ^= nums[i];
            else
                zero ^= nums[i];

            if(i+1 & (1&lt;<bitNo))
                one ^= i+1;
            else    
                zero ^= i+1;
        }

        int isOneRepeating = false;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==one)
                isOneRepeating = true;
        }

        if(isOneRepeating)
            return {one, zero};
        return {zero, one};
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Summary#

Approach	Time	Space	Overflow Risk	Modifies Array	Simplicity
Brute Force	O(n log n)	O(1)	No	Yes (if sorting)	Easy
Hashing	O(n)	O(n)	No	No	Easy
Math	O(n)	O(1)	Yes (use long long)	No	Medium
XOR	O(n)	O(1)	No	No	Medium-Hard

DSANon-overlapping IntervalsCovers: Greedy, DP. Optimal — Time O(n), Space O(1).DSAMerge IntervalsCovers: Linear scan, No extra Space. Optimal — Time O(n), Space O(1).DSAMeeting Rooms IIIIntervals problem — solution with code and analysis.

Brute Force Approach#

Better Approach#

Maths Approach#

Implementation#

XOR approach#

Summary#

Related articles