Missing Number — XOR or Gauss Formula
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
← Previous
Sum of Two Integers — Bit Addition