The O(n) Club: Two Oddballs, One XOR Trick – Solving Single Number III Without the Hashmap Hype

The O(n) Club: Two Oddballs, One XOR Trick – Solving Single Number III Without the Hashmap Hype

⚡ TL;DR

You’ve got an int array where everything is in pairs—except for two weirdos. Quick fix? You could summon a HashMap and count like it’s tax season, but you’d double your space and probably your regrets. Enter XOR: the ancient ninja move that cancels out doubles without a single memory leak.

// Brute-force HashMap, but why?
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
    count.put(num, count.getOrDefault(num, 0) + 1);
}
// Return all with count == 1
 // XOR-power version (O(n) time, O(1) space):
int xor = 0;
for (int n : nums) xor ^= n;
int mask = xor & -xor;
int a = 0;
for (int n : nums) if ((n & mask) != 0) a ^= n;
int b = xor ^ a; // voilà, your pair of loners!

🧠 How Devs Usually Mess This Up

If you’re like most devs staring at deadline o’clock, you reach for your trusty hashmap, count all the things, and call it a day. Too bad that wastes memory (and possibly your soul). Even funnier, some assume XOR only unearths a single odd number, and then get confused when it spits out nonsense. Others trip over which bit to partition on and spend an hour debugging their “genius idea” that never worked.

🔍 What’s Actually Going On

XOR is basically your nerdy bouncer: a ^ a = 0, so anything doubled gets zeroed out—leaving only the two unpaired party crashers. Here’s the spicy bit: xorAll = x ^ y, the XOR of our two outliers. If you find a bit where they differ, you can split the whole array into two squads and run XOR in each group: duplicates cancel, and each group reveals a unique. Think of it as a sock drawer where everyone’s got a twin except for two rebels, one with a hole, the other neon pink.

🛠️ PseudoCode

• XOR every number together.
  

  int xor = 0;
  for (int n : nums) xor ^= n;

  This gives you x ^ y—the combo of your oddballs.
• Find a set bit (anywhere x and y differ):
  

  int mask = xor & -xor;

  This magic picks out the rightmost ‘1’ bit.
• XOR all numbers where this bit is set.
  

  int a = 0;
  for (int n : nums)
      if ((n & mask) != 0) a ^= n;

  Now a is one of your lonely numbers.
• Recover the second one.
  

  int b = xor ^ a;

💻 The Code

public int[] singleNumber(int[] nums) {
    int xor = 0;
    for (int n : nums) xor ^= n;
    int mask = xor & -xor;
    int a = 0;
    for (int n : nums) if ((n & mask) != 0) a ^= n;
    int b = xor ^ a;
    return new int[]{a, b};
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Picking bits at random? Don’t. Use xor & -xor to grab the lowest differing bit. Anything else is roulette.
• Negative numbers? Java’s bit magic doesn’t care. Your negatives play nice here.
• Return order isn’t sacred. [a, b] or [b, a]—both are fine unless your interviewer is weirdly specific.
• Time/Space: Two lightning-fast passes, O(n) time, O(1) space. Even your smartwatch could run this.

🧠 Interviewer Brain-Tattoo

“Why use a sledgehammer HashMap when a precision XOR laser can do the job? Go bitwise, or go home.”