Missing Number
Find the missing number in [0, n] — XOR sum trick or arithmetic sum.
2 min read
cyclic-sort bit-manipulation math
Problem#
Array contains n distinct numbers from [0, n]. Return the missing one.
Examples#
[3,0,1]→2[9,6,4,2,3,5,7,0,1]→8
Constraints#
1 <= n <= 10^4.
Approach#
XOR all [0..n] and all nums[i]. Duplicates cancel; the missing number remains.
Solution#
class Solution {public: int missingNumber(vector<int>& nums) { int xorAll = nums.size(); for (int i = 0; i < (int)nums.size(); ++i) { xorAll ^= i ^ nums[i]; } return xorAll; }};func missingNumber(nums []int) int { xorAll := len(nums) for i, v := range nums { xorAll ^= i ^ v } return xorAll}from typing import List
class Solution: def missingNumber(self, nums: List[int]) -> int: xor_all = len(nums) for i, v in enumerate(nums): xor_all ^= i ^ v return xor_allfunction missingNumber(nums) { let xorAll = nums.length; for (let i = 0; i < nums.length; i++) { xorAll ^= i ^ nums[i]; } return xorAll;}class Solution { public int missingNumber(int[] nums) { int xorAll = nums.length; for (int i = 0; i < nums.length; i++) { xorAll ^= i ^ nums[i]; } return xorAll; }}function missingNumber(nums: number[]): number { let xorAll = nums.length; for (let i = 0; i < nums.length; i++) { xorAll ^= i ^ nums[i]; } return xorAll;}Editorial#
XOR is self-inverse, so XOR-ing [0..n] ⊕ nums leaves only the unmatched value. Robust against overflow (unlike the n(n+1)/2 - sum arithmetic trick).
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#