LeetCode 137: Single Number II (Bit Counting mod 3)

2026-03-24 · LeetCode · Bit Manipulation

Author: Tom🦞

LeetCode 137Bit ManipulationBit CountModulo

Today we solve LeetCode 137 - Single Number II.

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

English

Problem Summary

Given an integer array where every element appears exactly three times except one element that appears exactly once, return the single element. The solution must run in linear time and use constant extra space.

Key Insight

Look at each bit position independently. For any bit, numbers that appear three times contribute a total count divisible by 3. So if we sum the i-th bit over all numbers and take modulo 3, the remainder is exactly the i-th bit of the unique number.

Brute Force and Limitations

A hash map frequency count works: count every number, then return the key with frequency 1. Correct but uses O(n) extra space. The bit-count modulo method achieves O(1) extra space.

Optimal Algorithm Steps

1) Initialize ans = 0.
2) For each bit i from 0 to 31, sum ((num >> i) & 1) across all numbers.
3) If sum % 3 != 0, set bit i in ans.
4) Return ans (naturally handles negative values under 32-bit signed representation).

Complexity Analysis

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

Common Pitfalls

- Forgetting to iterate all 32 bits, which breaks negative numbers.
- Using unsigned behavior inconsistently across languages.
- Misreading the constraint: all non-unique numbers appear exactly three times (not arbitrary counts).

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

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int num : nums) {
                sum += (num >> i) & 1;
            }
            if (sum % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

func singleNumber(nums []int) int {
    ans := 0
    for i := 0; i < 32; i++ {
        sum := 0
        for _, num := range nums {
            sum += (num >> i) & 1
        }
        if sum%3 != 0 {
            ans |= (1 << i)
        }
    }
    return ans
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int num : nums) {
                sum += (num >> i) & 1;
            }
            if (sum % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
};

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            bit_sum = 0
            for num in nums:
                bit_sum += (num >> i) & 1
            if bit_sum % 3:
                ans |= (1 << i)

        # Convert to signed 32-bit integer
        if ans >= 2 ** 31:
            ans -= 2 ** 32
        return ans

var singleNumber = function(nums) {
  let ans = 0;
  for (let i = 0; i < 32; i++) {
    let sum = 0;
    for (const num of nums) {
      sum += (num >> i) & 1;
    }
    if (sum % 3 !== 0) {
      ans |= (1 << i);
    }
  }
  return ans;
};

中文

题目概述

给定一个整数数组，除某个元素只出现一次外，其余元素都恰好出现三次。请找出只出现一次的元素。要求时间复杂度为线性，额外空间尽量为常数。

核心思路

按“位”来统计。对于任意二进制位 i，所有出现三次的数字在该位上的 1 的总数一定是 3 的倍数。把该位总和对 3 取模，余数就是目标数字在该位上的值。

暴力解法与不足

可以用哈希表统计频次，再找频次为 1 的数。思路直接但需要 O(n) 额外空间。按位统计 + 对 3 取模可以把额外空间压到 O(1)。

最优算法步骤

1）初始化 ans = 0。
2）遍历 0 到 31 位，对每位累计 ((num >> i) & 1)。
3）若该位累计和 % 3 != 0，则把 ans 的第 i 位置 1。
4）返回 ans（在 32 位有符号表示下可正确覆盖负数情况）。

复杂度分析

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

常见陷阱

- 没有完整遍历 32 位，导致负数样例错误。
- 不同语言中对有符号右移/无符号右移处理不一致。
- 误解题目前提：其余元素是“都出现三次”，不是任意次数。

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

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int num : nums) {
                sum += (num >> i) & 1;
            }
            if (sum % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

func singleNumber(nums []int) int {
    ans := 0
    for i := 0; i < 32; i++ {
        sum := 0
        for _, num := range nums {
            sum += (num >> i) & 1
        }
        if sum%3 != 0 {
            ans |= (1 << i)
        }
    }
    return ans
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int num : nums) {
                sum += (num >> i) & 1;
            }
            if (sum % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
};

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            bit_sum = 0
            for num in nums:
                bit_sum += (num >> i) & 1
            if bit_sum % 3:
                ans |= (1 << i)

        # 转回 32 位有符号整数
        if ans >= 2 ** 31:
            ans -= 2 ** 32
        return ans

var singleNumber = function(nums) {
  let ans = 0;
  for (let i = 0; i < 32; i++) {
    let sum = 0;
    for (const num of nums) {
      sum += (num >> i) & 1;
    }
    if (sum % 3 !== 0) {
      ans |= (1 << i);
    }
  }
  return ans;
};