Find Missing Number In An Array Without Using Extra Space

Given an array of size n-1 which contains all the numbers within range 1 to n with exactly one number as missing. Find that missing number without using any extra space.

Test Cases

Test Case 1

Input: 1 2 4
Output: 3
Explanation: 3 is missing in the above array.

Test Case 2

Input: 1 3 4 5
Output: 2
Explanation: 2 is missing in the above array.

Solution

We can solve this problem easily by using the XOR operator and two of its most important properties.

1. a^a = 0: This means that when you take xor of a number with itself, you get 0.
2. a^0 = a: When you take xor of a number with 0, you get back the same number.

To find the missing number,
Let us compute the XOR of all the numbers from 1 to N.
XOR(1, 2, 3, 4, .... N) = X

Now let us compute the XOR of all the numbers present within the array.
XOR(1, 2, 3, ... N) = Y

If we compute XOR(X, Y), then all the numbers except the missing number will be there twice. According to property no 1, they will become 0.
Only the missing number will be there exactly once and therefore, according to property 2, it will be the only one which remains.

Therefore, the answer would be XOR(X, Y).

Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = { 1, 3, 4, 5 };
    int x = 0;
    for(int i = 1; i <= a.size() + 1; i++) {
        x = x^i;
    }
    int y = 0;
    for(int i = 0; i < a.size(); i++) {
        y = y^a[i];
    }

    cout << "The missing number is " << (x^y) << "\n";
}