Single Number II

Topic: 04. Bit Manipulation

Link: LeetCode 137 - Single Number II

1. Logical Breakdown

• [x] Core Logic: Track bits appearing 1x (ones) and 2x (twos).
• [x] Reset: If a bit appears 3x, clear it from both.

2. Visualization

graph TD Loop["For each num"] --> Update["Update ones & twos"] Update --> Reset["Mask bits appearing 3 times"] Reset --> Loop

3. Complexity

• Time: O(N)
• Space: O(1)

4. Code

package com.dsa.bitmanipulation;

public class SingleNumberII {
    public int solve(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}