Missing in Array

Given an array arr of size n−1 that contains distinct integers in the range of 1 to n (inclusive), find the missing element. The array is a permutation of size n with one element missing. Return the missing element.

Examples:

Input: n = 5, arr[] = [1,2,3,5]
Output: 4
Explanation : All the numbers from 1 to 5 are present except 4.

Input: n = 2, arr[] = [1]
Output: 2
Explanation : All the numbers from 1 to 2 are present except 2.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ n ≤ 10⁵
1 ≤ arr[i] ≤ n

Approach 01:

#include <iostream>  
#include<numeric> 

class Solution {
  public:
    int missingNumber(int n, vector<int>& arr) {
        int total;
        return ((n*(n+1))/2 - accumulate(arr.begin(), arr.end(), total));

    }
};

class Solution:
    def missingNumber(self, n, arr):
        return ((n*(n+1))//2 - sum(arr))

Time Complexity

• Calculating the Total Sum:

  The formula (n * (n + 1)) / 2 computes the sum of the first n natural numbers, which takes \( O(1) \) time.

• Calculating the Sum of the Array:

  The function accumulate is used to calculate the sum of all elements in the array arr. This operation takes \( O(n) \) time, where n is the number of elements in the input array arr (which is actually n - 1 since one number is missing).

• Overall Time Complexity:

  The overall time complexity is \( O(n) \) due to the summation of the elements in the array.

Space Complexity

• Space for Variables:

  Only a few integer variables (total) are used for calculation, which takes \( O(1) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), as the function uses a constant amount of additional space regardless of the input size.