Missing Number

Solved

Difficulty: Easy Accuracy: — Submissions: 0 Points: 2

You are given an array arr[] of n distinct integers taken from the range 1 to n+1. Exactly one number from that range is missing. Find it.

Examples:

Input: arr[] = [1, 2, 4, 5]

Output: 3

Explanation: The range is 1 to 5 and 3 is not in the array.

Input: arr[] = [2, 3, 1, 5]

Output: 4

Explanation: Every number from 1 to 5 is present except 4.

Constraints:

1 ≤ arr.size() ≤ 10^5
1 ≤ arr[i] ≤ arr.size() + 1

Expected Complexities

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

Company Tags

Adobe Amazon Microsoft

Topic Tags

Arrays Easy

The numbers 1 to n+1 add up to (n+1)(n+2)/2. Subtract the sum of the array from that and what is left is the missing number. Use a 64-bit sum to be safe with large n. An XOR of all indices and values gives the same result without any risk of overflow.

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