Missing Number

Find the missing number in [0, n] — XOR sum trick or arithmetic sum.

Easy
Time O(n) Space O(1)
LeetCode
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#

Missing Number
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.