Skip to content
AI360Xpert
Back to Bit Manipulation
Easy

Missing Number

Given an array `nums` containing `n` distinct numbers in the range `[0, n]`, return the only number in the range that is missing from the array.

Examples

Input:nums = [3,0,1]
Output:2
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Input:nums = [0,1]
Output:2
n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Input:nums = [9,6,4,2,3,5,7,0,1]
Output:8
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Bitwise XOR

Approach

We know that `a ^ a = 0` and `a ^ 0 = a`. If we XOR all the numbers from `0` to `n` and also XOR all the elements in the `nums` array, the numbers that are present in both will cancel each other out (become 0). The only number left will be the one that is missing from the `nums` array.

Complexity Analysis

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

Time complexity is O(n) as we iterate through the array once. Space complexity is O(1). Note that a Math approach using the sum formula `n*(n+1)/2` is also possible and optimal.

Solution.java
class Solution {    public int missingNumber(int[] nums) {        int res = nums.length; // Start with n                for (int i = 0; i < nums.length; i++) {            // XOR index i and the value at nums[i]            res = res ^ i ^ nums[i];        }                return res;    }}