Problem Statement

Given an array nums containing ndistinct numbers in the range [1, n],
return the only number in the range that is missing from the array.

Different Approaches

1️⃣ Brute Force Approach

The brute force approach involves iterating through the entire array and checking for each number's presence. This method has a time complexity of O(n^2) as we have to compare each element with other element.

Code:

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

int missingNumber(vector<int>&a, int N) {

    // Outer loop that runs from 1 to N:
    for (int i = 1; i <= N; i++) {

        // flag variable to check
        //if an element exists
        int flag = 0;

        //Search the element using linear search:
        for (int j = 0; j < N - 1; j++) {
            if (a[j] == i) {

                // i is present in the array:
                flag = 1;
                break;
            }
        }

        // check if the element is missing
        //i.e flag == 0:

        if (flag == 0) return i;
    }

    // The following line will never execute.
    // It is just to avoid warnings.
    return -1;
}

int main()
{
    int N = 5;
    vector<int> a = {1, 2, 4, 5};
    int ans = missingNumber(a, N);
    cout << "The missing number is: " << ans << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N ^ 2), In the worst case that is the missing number is N itself, the outer loop will run for N times, and for every single run the inner loop will also run.
• Space Complexity:O(1)

2️⃣ Using Hashing

Using the hashing technique, we will store the frequency of each element of the given array. Now, the number (i.e., between 1 to N) for which frequency will be 0, will be returned.

Code:

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

int missingNumber(vector<int>&a, int N) {

    int hash[N + 1] = {0}; // hash array

    // storing the frequencies:
    for (int i = 0; i < N - 1; i++)
        hash[a[i]]++;

    //checking the freqencies for numbers 1 to N:
    for (int i = 1; i <= N; i++) {
        if (hash[i] == 0) {
            return i;
        }
    }

    // The following line will never execute.
    // It is just to avoid warnings.
    return -1;
}

int main()
{
    int N = 5;
    vector<int> a = {1, 2, 4, 5};
    int ans = missingNumber(a, N);
    cout << "The missing number is: " << ans << endl;
    return 0;
}

// Output
The missing number is: 3

Complexity Analysis:

• Time Complexity:O(N) + O(N) ~ O(2N), where N = size of the array + 1
  • For storing the frequencies in the hash array, the program takes O(N)time complexity and for checking the frequencies in the second step again O(N) is required. So, the total time complexity is O(N)  + O(N)
• Space Complexity:O(N), where N = size of the array + 1. Here we are using an extra hash array of size N + 1

3️⃣ Mathematical Formula (Summation)

If the array contains numbers from 1 to N, we can use the sum of the first N natural numbers to find the missing number. Calculate the expected sum using the formula (N * (N + 1)) / 2 and subtract the sum of the array elements. The result will be the missing number.

Code:

#include <iostream>
#include <vector>

using namespace std;

int findMissingNumber(const vector<int>& nums) {
    int n = nums.size() + 1;
    int totalSum = n * (n + 1) / 2;
    int arraySum = 0;
    for (int num : nums) {
        arraySum += num;
    }
    return totalSum - arraySum;
}

int main() {
    vector<int> nums = {1, 2, 4, 5, 6};
    int missingNumber = findMissingNumber(nums);
    cout << "The missing number is: " << missingNumber << endl;
    return 0;
}

// Output
The missing number is: 3

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(1)

4️⃣ XOR Operation

The XOR operation has the property that XORing a number with itself results in 0. By XORing all array elements and XORing the result with the XOR of the first N natural number, the missing number can be obtained.

Intuition:

Another optimal approach, uses the below property of XOR to find the missing number.

• XOR of two same numbers is 0.
• The XOR of a number with 0 is the number itself

Understand that on calculating the XOR of all numbers from 1 to N we make sure that each number is included. After that on calculating the XOR of all the elements in the array & then performing XOR these two results, all the numbers present in the final result will appear twice expect for the one which is missing. Hence the number occurring twice turn out 0 satisfying first condition, and then followed by 0 ^ missing number, leaving the missing number itself.

Approach:

1. Initialize two variables xor1, xor2 as 0. xor1 variable will calculate the XOR of 1 to N
2. Calculate the XOR of all the elements in the array by xor2 = xor2 ^ arr[i]..
3. Finally, the answer will be the XOR of xor1 and xor2.

Code:

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

int missingNumber(vector<int>&a, int N) {

    int xor1 = 0, xor2 = 0;

    for (int i = 0; i < N - 1; i++) {
        xor2 = xor2 ^ a[i]; // XOR of array elements
        xor1 = xor1 ^ (i + 1); //XOR up to [1...N-1]
    }
    xor1 = xor1 ^ N; //XOR up to [1...N]

    return (xor1 ^ xor2); // the missing number
}

int main()
{
    int N = 5;
    vector<int> a = {1, 2, 4, 5};
    int ans = missingNumber(a, N);
    cout << "The missing number is: " << ans << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N), where N = size of array + 1
  • Here, we need only 1 loop to calculate the XOR. The loop runs for approx. N times. So, the time complexity is O(N).
• Space Complexity:O(1) as we are not using any extra space.

Method 4: Cyclic Sort

The Cyclic Sort algorithm can be used to find the missing number in an array containing unique integers in the range from 0 to n.

#include <iostream>
#include <vector>

int findMissingNumber(std::vector<int>& nums) {
    int i = 0;
    while (i < nums.size()) {
        if (nums[i] < nums.size() && nums[i] != nums[nums[i]]) {
            std::swap(nums[i], nums[nums[i]]);
        } else {
            i++;
        }
    }
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != i) {
            return i;
        }
    }
    return nums.size();
}

int main() {
    std::vector<int> nums = {3, 0, 1};
    std::cout << "Missing number: " << findMissingNumber(nums) << std::endl;
    return 0;
}

Derivative

Problem Statement

You are given an array nums containing n distinct numbers in the range [0, n]. The array is missing exactly one number from this range. Your task is to find and return the missing number.

Examples

Example 1:

Input: nums = [3, 0, 1]
Output: 2

Explanation: The range is [0, 3], and the number 2 is missing.

Example 2:

Input: nums = [0, 1]
Output: 2

Explanation: The range is [0, 2], and the number 2 is missing.

Example 3:

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8

Explanation: The range is [0, 9], and the number 8 is missing.

Example 4:

Input: nums = [0]
Output: 1

Explanation: The range is [0, 1], and the number 1 is missing.

Different Approaches

1️⃣ Sum Formula

Intuition:

The sum of numbers from 0 to n is given by the formula:

Sum = n * (n + 1) / 2

The difference between their sum and the sum of the elements in the array gives the missing number.

Code:

#include <iostream>
#include <vector>
using namespace std;

int missingNumberSumFormula(vector<int>& nums) {
    int n = nums.size();
    int totalSum = n * (n + 1) / 2;
    int arraySum = 0;

    for (int num : nums) {
        arraySum += num;
    }

    return totalSum - arraySum;
}

int main() {
    vector<int> nums = {3, 0, 1};
    cout << "Missing number: " << missingNumberSumFormula(nums) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • Calculate the array sum in a single traversal.
• Space Complexity: O(1)
  • No extra space is used.

2️⃣ Using XOR

Intuition:

• XOR has the property that x ^ x = 0 and x ^ 0 = x.
• XOR all the numbers in the range [0, n] with the numbers in the array.
• The result will be the missing number.

Code:

#include <iostream>
#include <vector>
using namespace std;

int missingNumberXOR(vector<int>& nums) {
    int n = nums.size();
    int xorAll = 0, xorNums = 0;

    for (int i = 0; i <= n; ++i) {
        xorAll ^= i;
    }
    for (int num : nums) {
        xorNums ^= num;
    }

    return xorAll ^ xorNums;
}

Complexity Analysis:

• Time Complexity: O(n)
  • Single traversal to compute XOR
• Space Complexity: O(1)
  • No extra space is used.