The O(n) Club: Single Number II: That One Rogue Bit Nobody Likes

The O(n) Club: Single Number II—That One Rogue Bit Nobody Likes

⚡ TL;DR

Given an array where every number appears three times except one lonely misfit, your job is to find the outlier. You get O(n) time, O(1) space, and strictly no hashmaps, no “just XOR it” shortcuts. Brute force is for warmups only:

// Slow & sad: HashMaps won't sneak past O(1) space
default
Map<Integer, Integer> count = new HashMap<>();
for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);
for (int n : count.keySet()) if (count.get(n) == 1) return n;

🧠 How Devs Usually Mess This Up

Most folks reach for XOR (thanks Single Number I), but triplets break that party trick. Then your brain suggests hashmaps—which, if O(1) space means nothing to you, go for it—but your interviewer will glare so hard you’ll feel it in your stack. The trick is, neither brute force nor classic XOR fly here.

🔍 What’s Actually Going On

Think of each int as a chef walking into a kitchen—every chef brings 32 secret ingredients (their bits). Count up how much of ingredient #1, #2…#32 you get. Since all regulars come in sets of three, their ingredients’ total will be a multiple of 3. Only our rebel chef (the unique number) throws off the recipe. So, count each bit position, mod by 3; any remaining ‘spice’ belongs to your oddball. Voila: Bitwise Detective Work 101.

🛠️ PseudoCode

• Set result = 0
• For each of 32 bits (0 to 31):
  • Count how many numbers have that bit set.
  • If count % 3 != 0, set that bit in result.
• If the sign bit (31st) is set, fix result for negative numbers.

// Bitwise mod 3 detective
for (int i = 0; i < 32; i++) {
    int bitCount = 0;
    for (int num : nums)
        bitCount += (num >> i) & 1;
    if (bitCount % 3 != 0)
        result |= (1 << i);
}
// Fix for negatives
if ((result & (1 << 31)) != 0)
    result -= (1L << 32);

• This works because the unique number is the only one with leftovers after triplets are cleaned up at every bit position.

💻 The Code

public int singleNumber(int[] nums) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        int bitCount = 0;
        for (int num : nums) {
            bitCount += (num >> i) & 1;
        }
        if (bitCount % 3 != 0) {
            result |= (1 << i);
        }
    }
    // Correction for negative numbers in Java
    if ((result & (1 << 31)) != 0) {
        result -= (1L << 32);
    }
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Negative numbers: Java’s int is signed, so handle the overflow—see code’s post-processing.
• HashMaps: Your O(1) space dreams will cry. Don’t do it.
• XOR trickery: Triple appearances break its magic; XOR’s only for twins, not triplets.
• Complexity check: You’re doing 32 rounds of n—call it O(n) and bask in your efficiency. Space? You’re using a handful of ints: pure O(1).

🧠 Interviewer Brain-Tattoo

“When counting numbers fails, count bits. Rogue bits never pretend to fit society.”