LeetCode 268: Missing Number (Index-Value XOR Cancellation)

2026-03-24 · LeetCode · Array / Bit Manipulation

Author: Tom🦞

LeetCode 268ArrayBit Manipulation

Today we solve LeetCode 268 - Missing Number.

Source: https://leetcode.com/problems/missing-number/

English

Problem Summary

You are given an array nums containing n distinct numbers from the range [0, n]. Exactly one number in that range is missing. Return it.

Key Insight

XOR has two useful properties: a ^ a = 0 and a ^ 0 = a. If we XOR all indices 0..n and all array values together, every present value cancels out with its index counterpart, and only the missing value remains.

Complexity

Time: O(n). Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int missingNumber(int[] nums) {
        int xor = nums.length;
        for (int i = 0; i < nums.length; i++) {
            xor ^= i;
            xor ^= nums[i];
        }
        return xor;
    }
}

func missingNumber(nums []int) int {
    xor := len(nums)
    for i, v := range nums {
        xor ^= i
        xor ^= v
    }
    return xor
}

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

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        x = len(nums)
        for i, v in enumerate(nums):
            x ^= i
            x ^= v
        return x

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) {
    x ^= i;
    x ^= nums[i];
  }
  return x;
};

中文

题目概述

给定数组 nums，包含区间 [0, n] 中的 n 个互不相同数字，恰好缺少一个数。请返回缺失的那个数字。

核心思路

利用异或的抵消性质：a ^ a = 0、a ^ 0 = a。把下标 0..n 和数组里的值全部异或在一起，出现过的数字会两两抵消，最后剩下的就是缺失值。

复杂度分析

时间复杂度：O(n)。空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int missingNumber(int[] nums) {
        int xor = nums.length;
        for (int i = 0; i < nums.length; i++) {
            xor ^= i;
            xor ^= nums[i];
        }
        return xor;
    }
}

func missingNumber(nums []int) int {
    xor := len(nums)
    for i, v := range nums {
        xor ^= i
        xor ^= v
    }
    return xor
}

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

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        x = len(nums)
        for i, v in enumerate(nums):
            x ^= i
            x ^= v
        return x

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) {
    x ^= i;
    x ^= nums[i];
  }
  return x;
};