Missing Number

Problem

Ritu has all numbers from 1 to n in an array arr of length n-1 except one number. You have to find which number, Ritu doesn't have from 1 to n.

NOTE: Don't use Sorting

Examples:

Example 1:

Input:
n  =  4                                        
arr = {1, 4, 3}
Output: 2     
Explanation:
Ritu doesn't have number 2

Example 2:

Input:                        
n = 5
arr = {2, 5, 3, 1}
Output: 4
Explanation:
Ritu doesn't have number 4 in her collection

Your task:

You don't need to read input or print anything. Your task is to complete the function missingNumber() which takes an integer n and an array arr of length n-1 as inputs and returns the missing number.

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

Constraints:

• $2 ≤ n ≤ 10^4$
• $1 ≤ arr[i] ≤ n$
• $Size(arr) = n-1$

Solution

Python

def missingNumber(self, n : int, arr : List[int]) -> int:
    total_sum = n * (n + 1) // 2
    array_sum = sum(arr)
    return total_sum - array_sum

Java

public static int missingNumber(int n, int[] arr) {
    int total_sum = n * (n + 1) / 2;
    int array_sum = 0;
    for(int i = 0; i<arr.length; i++)
        array_sum+=arr[i];
    int result = total_sum - array_sum;
    return result;
}

C++

int missingNumber(int n, vector<int> &arr) {
    int total_sum = n * (n + 1) / 2;
    int array_sum = 0;
    for (int i = 0; i < arr.size(); i++) {
        array_sum += arr[i];
    }
    int result = total_sum - array_sum;
    return result;
}

C

int missingNumber(int n, int arr[], int size) {
    int total_sum = n * (n + 1) / 2;
    int array_sum = 0;
    for (int i = 0; i < size; i++) {
        array_sum += arr[i];
    }
    int result = total_sum - array_sum;
    return result;
}

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