The O(n) Club: Single Number — How XOR Outsmarts Everyone at the Coding Party

The O(n) Club: Single Number — How XOR Outsmarts Everyone at the Coding Party

⚡ TL;DR

The infamous Single Number problem: there’s one oddball in an int array (he shows up once while everyone else is there with their plus-ones). Most people grab a hashmap or start sorting. The clever just XOR everything and stroll out with the answer. Here’s how that looks (spoiler: it’s boringly elegant):

// Returns the unique number in nums
int singleNumber(int[] nums) {
    int result = 0;
    for (int n : nums) {
        result ^= n;
    }
    return result;
}

🧠 How Devs Usually Mess This Up

You’re sleep-deprived, the coffee has gone cold, so you pull out a HashMap for counting, or you sort the entire array just to compare neighboring numbers. Maybe you do a brute-force double loop—hey, who needs CPU cycles anyway? The result: wasted time, wasted space, and an interviewer who’s seen it all before and still won’t laugh at your memes.

🔍 What’s Actually Going On

Ready for some bit-tastic wisdom? XOR (^ in Java):

• a ^ a = 0 (any number XOR itself vanishes—like mutually assured destruction for numbers)
• a ^ 0 = a (XOR with zero is zero calories—no effect)
• Order doesn’t matter (commutative and associative—your code’s version of jazz improvisation)

So, XOR everything together: every pair dissolves to zero, and you’re left with the lone survivor. No sorting. No extra memory. No crime scene tape.

🛠️ PseudoCode

• Start with result = 0 (zero drama)
• Loop for every number n in nums: Set result = result ^ n
• Return result (congratulate yourself quietly)

// Basically Java, but imagine me saying it with jazz hands
int result = 0;
for each n in nums:
    result = result ^ n;
return result;

💻 The Code

public class SingleNumber {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int n : nums) {
            result ^= n;
        }
        return result;
    }
     public static void main(String[] args) {
        int[] nums = {2, 3, 5, 4, 5, 3, 4};
        System.out.println(new SingleNumber().singleNumber(nums)); // Output: 2
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• If numbers appear three times (or more than one single), XOR checks out and leaves chaos behind. This is strictly “two’s company, one’s alone.”
• Resist array mutation and extra arrays—your memory budget and future you will thank you.
• This only works for the classic prompt. Variants? You’ll need new tricks (and maybe existential therapy).
• O(n) time and O(1) space—actual interview gold. Brute force and hash maps are just “how to write more bugs.”

🧠 Interviewer Brain-Tattoo

“For Single Number, if you reach for a hash map, the bits quietly weep. XOR: because sometimes, ‘clever’ means just knowing your computer’s favorite party trick.”