Missing Number — XOR or Gauss Formula

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem

Given an array containing n distinct numbers in range [0,n], find the missing number.


Solutions

Python — XOR

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        res=len(nums)
        for i,n in enumerate(nums): res^=i^n
        return res

Python — Math

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n=len(nums)
        return n*(n+1)//2 - sum(nums)

C++

class Solution {
public:
    int missingNumber(vector<int>& nums){
        int n=nums.size(),res=n;
        for(int i=0;i<n;i++) res^=i^nums[i];
        return res;
    }
};

Complexity

  • Time: O(n) | Space: O(1)

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro