Missing Number

You are given an array nums containing n distinct numbers taken from the range [0, n]. The array has one missing number from this range. Find the missing number.

Sample Input and Expected Output:

Input:

nums = [3, 0, 1]

Output:

The missing number is: 2

Input:

nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]

Output:

The missing number is: 8

Missing Number Solution in C++:

The idea is to use the sum of the first n natural numbers and subtract the sum of the given array from it. The difference will be the missing number.

#include <iostream>
#include <vector>

int missingNumber(std::vector<int>& nums) {
    int n = nums.size();
    int sum = n * (n + 1) / 2; // Sum of the first n natural numbers.

    for (int num : nums) {
        sum -= num; // Subtract the sum of the array from the sum of the first n natural numbers.
    }

    return sum;
}

int main() {
    std::vector<int> nums1 = {3, 0, 1};
    std::vector<int> nums2 = {9, 6, 4, 2, 3, 5, 7, 0, 1};

    int result1 = missingNumber(nums1);
    int result2 = missingNumber(nums2);

    std::cout << "The missing number is: " << result1 << std::endl;
    std::cout << "The missing number is: " << result2 << std::endl;

    return 0;
}

Missing Number Time Complexity and Space Complexity:

The time complexity of the solution is O(n), where n is the size of the input vector nums. We need to iterate through the array once to calculate the sum.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The algorithm does not use any extra data structures.