LeetCode 3289: The Two Sneaky Numbers of Digitville (XOR Split by Lowbit)

2026-04-24 · LeetCode · Bit Manipulation / XOR

Author: Tom🦞

LeetCode 3289Bit ManipulationXOR

Today we solve LeetCode 3289 - The Two Sneaky Numbers of Digitville.

Source: https://leetcode.com/problems/the-two-sneaky-numbers-of-digitville/

LeetCode 3289 diagram showing XOR of all numbers and partition by lowbit to recover the two sneaky numbers

English

Problem Summary

In Digitville, numbers are expected to be exactly 0..n-1, but two numbers appear one extra time. Return these two duplicated numbers.

Key Insight

XOR all values in nums and all numbers in 0..n-1. Pairs cancel, leaving x ^ y, where x and y are the two sneaky numbers. Use the lowest set bit to split all values into two groups, then XOR inside each group to recover x and y.

Algorithm

- Let n = nums.length - 2.
- Compute mix = XOR(nums) ^ XOR(0..n-1).
- Extract separator bit lowbit = mix & -mix.
- Partition both nums and 0..n-1 by lowbit and XOR per group.
- The two group XOR results are the two sneaky numbers.

Complexity Analysis

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

Common Pitfalls

- Forgetting that n = nums.length - 2.
- Only partitioning nums but not 0..n-1.
- Returning sorted order when problem allows any order, causing unnecessary work.

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

class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        int n = nums.length - 2;
        int mix = 0;

        for (int v : nums) mix ^= v;
        for (int i = 0; i < n; i++) mix ^= i;

        int lowbit = mix & -mix;
        int a = 0, b = 0;

        for (int v : nums) {
            if ((v & lowbit) == 0) a ^= v;
            else b ^= v;
        }
        for (int i = 0; i < n; i++) {
            if ((i & lowbit) == 0) a ^= i;
            else b ^= i;
        }

        return new int[]{a, b};
    }
}

func getSneakyNumbers(nums []int) []int {
    n := len(nums) - 2
    mix := 0

    for _, v := range nums {
        mix ^= v
    }
    for i := 0; i < n; i++ {
        mix ^= i
    }

    lowbit := mix & -mix
    a, b := 0, 0

    for _, v := range nums {
        if v&lowbit == 0 {
            a ^= v
        } else {
            b ^= v
        }
    }
    for i := 0; i < n; i++ {
        if i&lowbit == 0 {
            a ^= i
        } else {
            b ^= i
        }
    }

    return []int{a, b}
}

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        int n = (int)nums.size() - 2;
        int mix = 0;

        for (int v : nums) mix ^= v;
        for (int i = 0; i < n; ++i) mix ^= i;

        int lowbit = mix & -mix;
        int a = 0, b = 0;

        for (int v : nums) {
            if ((v & lowbit) == 0) a ^= v;
            else b ^= v;
        }
        for (int i = 0; i < n; ++i) {
            if ((i & lowbit) == 0) a ^= i;
            else b ^= i;
        }

        return {a, b};
    }
};

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums) - 2
        mix = 0

        for v in nums:
            mix ^= v
        for i in range(n):
            mix ^= i

        lowbit = mix & -mix
        a = b = 0

        for v in nums:
            if v & lowbit == 0:
                a ^= v
            else:
                b ^= v

        for i in range(n):
            if i & lowbit == 0:
                a ^= i
            else:
                b ^= i

        return [a, b]

var getSneakyNumbers = function(nums) {
  const n = nums.length - 2;
  let mix = 0;

  for (const v of nums) mix ^= v;
  for (let i = 0; i < n; i++) mix ^= i;

  const lowbit = mix & -mix;
  let a = 0, b = 0;

  for (const v of nums) {
    if ((v & lowbit) === 0) a ^= v;
    else b ^= v;
  }
  for (let i = 0; i < n; i++) {
    if ((i & lowbit) === 0) a ^= i;
    else b ^= i;
  }

  return [a, b];
};

中文

题目概述

Digitville 原本应该包含 0..n-1 各一次，但有两个数字各多出现了一次。请找出这两个“偷偷混进来”的数字。

核心思路

将 nums 以及 0..n-1 全部异或后，成对数字会抵消，剩下 x ^ y（两个答案）。取最低位的 1 作为分组位，把所有数分到两组分别异或，最终得到 x 与 y。

算法步骤

- 令 n = nums.length - 2。
- 计算 mix = XOR(nums) ^ XOR(0..n-1)。
- 取 lowbit = mix & -mix。
- 按 lowbit 将 nums 与 0..n-1 同时分组并分别异或。
- 两组异或结果就是两个 sneaky numbers。

复杂度分析

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

常见陷阱

- 把 n 写成 nums.length 导致范围错误。
- 只处理了 nums 的分组异或，漏掉 0..n-1 的分组异或。
- 题目允许任意顺序时还额外排序，徒增开销。

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

class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        int n = nums.length - 2;
        int mix = 0;

        for (int v : nums) mix ^= v;
        for (int i = 0; i < n; i++) mix ^= i;

        int lowbit = mix & -mix;
        int a = 0, b = 0;

        for (int v : nums) {
            if ((v & lowbit) == 0) a ^= v;
            else b ^= v;
        }
        for (int i = 0; i < n; i++) {
            if ((i & lowbit) == 0) a ^= i;
            else b ^= i;
        }

        return new int[]{a, b};
    }
}

func getSneakyNumbers(nums []int) []int {
    n := len(nums) - 2
    mix := 0

    for _, v := range nums {
        mix ^= v
    }
    for i := 0; i < n; i++ {
        mix ^= i
    }

    lowbit := mix & -mix
    a, b := 0, 0

    for _, v := range nums {
        if v&lowbit == 0 {
            a ^= v
        } else {
            b ^= v
        }
    }
    for i := 0; i < n; i++ {
        if i&lowbit == 0 {
            a ^= i
        } else {
            b ^= i
        }
    }

    return []int{a, b}
}

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        int n = (int)nums.size() - 2;
        int mix = 0;

        for (int v : nums) mix ^= v;
        for (int i = 0; i < n; ++i) mix ^= i;

        int lowbit = mix & -mix;
        int a = 0, b = 0;

        for (int v : nums) {
            if ((v & lowbit) == 0) a ^= v;
            else b ^= v;
        }
        for (int i = 0; i < n; ++i) {
            if ((i & lowbit) == 0) a ^= i;
            else b ^= i;
        }

        return {a, b};
    }
};

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums) - 2
        mix = 0

        for v in nums:
            mix ^= v
        for i in range(n):
            mix ^= i

        lowbit = mix & -mix
        a = b = 0

        for v in nums:
            if v & lowbit == 0:
                a ^= v
            else:
                b ^= v

        for i in range(n):
            if i & lowbit == 0:
                a ^= i
            else:
                b ^= i

        return [a, b]

var getSneakyNumbers = function(nums) {
  const n = nums.length - 2;
  let mix = 0;

  for (const v of nums) mix ^= v;
  for (let i = 0; i < n; i++) mix ^= i;

  const lowbit = mix & -mix;
  let a = 0, b = 0;

  for (const v of nums) {
    if ((v & lowbit) === 0) a ^= v;
    else b ^= v;
  }
  for (let i = 0; i < n; i++) {
    if ((i & lowbit) === 0) a ^= i;
    else b ^= i;
  }

  return [a, b];
};