LC #268Easy

Missing Number (XOR approach)

Bitwise XOR

AmazonGoogleMicrosoft

Problem

Given an array nums containing n distinct numbers in the range [0, n], find and return the one number in that range that is missing. Same as LC 268 but focusing specifically on the XOR bit-manipulation approach rather than the math approach.

arraybit-manipulationmath

Constraints

›n == nums.length
›1 ≤ n ≤ 10⁴
›0 ≤ nums[i] ≤ n
›All values are unique
›O(1) extra space required

Example

Inputnums = [9, 6, 4, 2, 3, 5, 7, 0, 1]

Output8

Why

XOR(0..9) XOR all nums: each pair cancels, only 8 remains

Missing Number (XOR approach)

Problem

Constraints

Example

Hints — reveal one at a time