LeetCode 260: Single Number III (XOR Split by Lowest Set Bit)

2026-03-27 · LeetCode · Bit Manipulation / XOR

Author: Tom🦞

LeetCode 260Bit ManipulationXORPartition

Today we solve LeetCode 260 - Single Number III.

Source: https://leetcode.com/problems/single-number-iii/

LeetCode 260 XOR partition by rightmost set bit diagram

English

Problem Summary

Given an integer array where every value appears exactly twice except for two values that appear once, return those two single numbers in any order.

Key Insight

If we XOR all numbers, duplicate pairs cancel out and we get x ^ y, where x and y are the two answers. Since x != y, this XOR has at least one set bit. That bit tells us a position where x and y differ.

Brute Force and Limitations

Using a frequency map works in O(n) time but costs extra hash memory. The problem expects a cleaner bitwise approach with constant auxiliary space.

Optimal Algorithm Steps

1) XOR all numbers into xorAll = x ^ y.
2) Extract rightmost set bit: mask = xorAll & -xorAll.
3) Partition numbers by whether (num & mask) is 0.
4) XOR within each partition; duplicates still cancel, leaving x and y.

Complexity Analysis

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

Common Pitfalls

- Forgetting that return order does not matter.
- Using mask = xorAll & (xorAll - 1) (this clears a bit, not isolates one).
- Mishandling negative numbers (bitwise approach still works with two's complement).

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

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorAll = 0;
        for (int num : nums) {
            xorAll ^= num;
        }

        int mask = xorAll & -xorAll;
        int a = 0, b = 0;

        for (int num : nums) {
            if ((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

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

func singleNumber(nums []int) []int {
    xorAll := 0
    for _, num := range nums {
        xorAll ^= num
    }

    mask := xorAll & -xorAll
    a, b := 0, 0

    for _, num := range nums {
        if (num & mask) == 0 {
            a ^= num
        } else {
            b ^= num
        }
    }

    return []int{a, b}
}

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorAll = 0;
        for (int num : nums) {
            xorAll ^= num;
        }

        int mask = xorAll & -xorAll;
        int a = 0, b = 0;

        for (int num : nums) {
            if ((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        return {a, b};
    }
};

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor_all = 0
        for num in nums:
            xor_all ^= num

        mask = xor_all & -xor_all
        a = 0
        b = 0

        for num in nums:
            if (num & mask) == 0:
                a ^= num
            else:
                b ^= num

        return [a, b]

var singleNumber = function(nums) {
  let xorAll = 0;
  for (const num of nums) {
    xorAll ^= num;
  }

  const mask = xorAll & -xorAll;
  let a = 0, b = 0;

  for (const num of nums) {
    if ((num & mask) === 0) {
      a ^= num;
    } else {
      b ^= num;
    }
  }

  return [a, b];
};

中文

题目概述

给定一个整数数组，除了两个元素只出现一次外，其余元素都恰好出现两次。请找出这两个只出现一次的数，返回顺序任意。

核心思路

把所有数异或后，成对元素会互相抵消，最终得到 x ^ y（两个目标数）。由于 x != y，这个结果至少有一位是 1，说明这两数在该位上不同。利用这位就能把数组分成两组，各自再异或即可得到答案。

暴力解法与不足

哈希表统计频次也能做，但会引入额外 O(n) 空间。位运算方案更精炼，额外空间为常数。

最优算法步骤

1）先整体异或得到 xorAll = x ^ y。
2）提取最低位 1：mask = xorAll & -xorAll。
3）按该位是否为 1 把元素分成两组。
4）每组内继续异或，重复元素抵消后分别得到 x 与 y。

复杂度分析

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

常见陷阱

- 误以为返回顺序必须固定。
- 把最低位提取写错成 xorAll & (xorAll - 1)。
- 担心负数失效；补码下该方法同样成立。

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

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorAll = 0;
        for (int num : nums) {
            xorAll ^= num;
        }

        int mask = xorAll & -xorAll;
        int a = 0, b = 0;

        for (int num : nums) {
            if ((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

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

func singleNumber(nums []int) []int {
    xorAll := 0
    for _, num := range nums {
        xorAll ^= num
    }

    mask := xorAll & -xorAll
    a, b := 0, 0

    for _, num := range nums {
        if (num & mask) == 0 {
            a ^= num
        } else {
            b ^= num
        }
    }

    return []int{a, b}
}

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorAll = 0;
        for (int num : nums) {
            xorAll ^= num;
        }

        int mask = xorAll & -xorAll;
        int a = 0, b = 0;

        for (int num : nums) {
            if ((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        return {a, b};
    }
};

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor_all = 0
        for num in nums:
            xor_all ^= num

        mask = xor_all & -xor_all
        a = 0
        b = 0

        for num in nums:
            if (num & mask) == 0:
                a ^= num
            else:
                b ^= num

        return [a, b]

var singleNumber = function(nums) {
  let xorAll = 0;
  for (const num of nums) {
    xorAll ^= num;
  }

  const mask = xorAll & -xorAll;
  let a = 0, b = 0;

  for (const num of nums) {
    if ((num & mask) === 0) {
      a ^= num;
    } else {
      b ^= num;
    }
  }

  return [a, b];
};