INTUITION:

The array is supposed to contain all numbers from 0 to n. Since one number is missing, we can use the sum of the first n natural numbers to deduce which number is missing.By subtracting the sum of all elements in the array from this total sum, we can find the missing number.

APPROACH:

• First, we calculate the total sum from 0 to n by adding all numbers in this range.
• Next, we compute the actual sum by adding all numbers present in the array.
• Finally, we subtract the actual sum from the total sum to find the missing number.

Time Complexity:O(N)

Space Complexity:O(1)

Here’s the code:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n=nums.size();
        int actual_sum=0;
        for(int i=0;i<n;i++)
        {
            actual_sum+=nums[i];
        }
        int total_sum=(n*(n+1))/2;
        return total_sum-actual_sum;
        
    }
};

KEYPOINTS:

• Mathematical Formula:

  • The sum of the first n numbers (from 0 to n) is calculated using the formula:

    Total sum = (n × (n + 1)) ÷ 2

  • This formula gives the sum as if no number were missing.

• Actual Sum Calculation:
  • We iterate through the array and sum up all its elements. This gives us the total of all numbers present in the array.
• Difference Calculation:
  • The missing number is the difference between the total sum (calculated using the formula) and the actual sum (calculated from the array).