Interview Classic 150 Problems P137 Single Number II

---

Timeline

Timeline

2025-11-25

init

Bit manipulation

---

Problem:

P137 Single Number II

https://leetcode.cn/problems/single-number-ii/description/?envType=study-plan-v2&envId=top-interview-150

For XOR, if a number x appears multiple times:

x ^ x = 0
x ^ x ^ x = x
x ^ x ^ x ^ x = 0
…
So: even count ⇒ cancels to 0, odd count ⇒ leaves 1 x
It can be understood from a deeper perspective: XOR is a ‘carry-free addition mod 2’

For example:

• 1 ^ 1 = (1 + 1) mod 2 = 0
• 1 ^ 1 ^ 1 = (1 + 1 + 1) mod 2 = 1
  This perfectly fits:
• Even occurrences → mod 2 = 0
• Odd occurrences → mod 2 = x

But in the problem, other numbers appear three times, so we need to take modulo 3:

• For each bit (0/1), among three identical numbers, this bit appears three times:
  • If this bit is 0: 0+0+0 = 0 (mod 3)
  • If this bit is 1: 1+1+1 = 3 ≡ 0 (mod 3)

This whole process is equivalent to:Adding each bit and performing modulo 3 operation。

#include <vector>
using std::vector;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        int total = 0;
        for (int i = 0; i < 32; ++i) {
            total = 0;
            for (int num: nums)
                total += ((num >> i) & 0x1);

            if (total % 3)
                ans |= (0x1 << i);

        }
        return ans;
    }
};