Single Number

Concept

LeetCode #136.
Problem: Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

Input: nums = [4, 1, 2, 1, 2]
Output: 4

If we didn’t have the $O(1)$ space constraint, this is a trivial Hash Map problem. You tally the frequencies, and return the key with a value of 1.
But because we cannot allocate any extra memory arrays or Hash Maps, we must use Bit Manipulation.

The Strategy

This problem was practically designed to test your knowledge of XOR (^).

Recall the mathematical properties of XOR:

1. Cancellation: X ^ X = 0. Any number XORed against itself completely annihilates into zero.
2. Identity: X ^ 0 = X. Any number XORed against zero remains completely unchanged.
3. Commutativity: A ^ B ^ C = A ^ C ^ B. The order in which you XOR numbers absolutely does not matter.

If the array is [4, 1, 2, 1, 2].
If we just blindly XOR every single number in the entire array together:
4 ^ 1 ^ 2 ^ 1 ^ 2

Because order doesn’t matter, we can mathematically rearrange this in our heads:
1 ^ 1 ^ 2 ^ 2 ^ 4

• 1 ^ 1 cancels out to 0.
• 2 ^ 2 cancels out to 0.
• The equation is now 0 ^ 0 ^ 4.
• 0 ^ 0 is 0.
• 0 ^ 4 is 4!

The pairs flawlessly annihilate each other, leaving only the lone survivor!

Implementation

// Time Complexity: O(N) (One pass through the array)
// Space Complexity: O(1) (Only a single integer variable)

function singleNumber(nums: number[]): number {
    let result = 0; // 0 ^ X is just X, making it the perfect starting point

    for (let i = 0; i < nums.length; i++) {
        // XOR the current number into the running result
        result = result ^ nums[i];
    }

    // The pairs cancelled out. The result holds the single number!
    return result;
}

Single Number II (The Upgrade)

LeetCode #137. Problem: Every element appears THREE times except for one, which appears exactly once. Find that single one.

The simple XOR trick instantly breaks here. X ^ X ^ X does not cancel to 0. It cancels to 0 ^ X, which is X. The triplets do not annihilate.

The Strategy for Triplets:
You must manually simulate the math. You create a loop of 32 bits.
For each column (0 to 31), you iterate through the entire array and count how many 1s exist in that specific column across all numbers.
Because every number appears 3 times, the total count of 1s in any given column MUST be a multiple of 3! (e.g., 9, 12, 15).
If the total count is NOT perfectly divisible by 3 (e.g., 10), it mathematically proves that the “Single Number” contributed a 1 to this specific column! We use the bitwise OR | operator to manually reconstruct the Single Number bit by bit.

function singleNumberTriplets(nums: number[]): number {
    let result = 0;

    // Check all 32 bit columns
    for (let i = 0; i < 32; i++) {
        let sum = 0;
        
        // Count the 1s in this specific column across all numbers
        for (const num of nums) {
            // Shift the number right by i, AND it with 1 to extract the bit
            sum += (num >> i) & 1;
        }

        // If the sum is NOT a multiple of 3, the Single Number has a 1 here!
        if (sum % 3 !== 0) {
            // Forcefully turn on the ith bit in our result
            result = result | (1 << i);
        }
    }

    return result;
}

Interview Questions

Q: In the XOR approach, does it matter if the array contains negative numbers?
A: No! XOR operates on the raw 32-bit binary structure (including the Sign Bit). A negative number A XORed against the exact same negative number A will perfectly cancel out the Sign Bits and all internal bits to 0.

Q: A developer suggests using the array.reduce((acc, curr) => acc ^ curr, 0) method for Single Number I. Is this acceptable?
A: Yes, this is a brilliant and highly idiomatic JavaScript one-liner. It executes in $O(N)$ time and perfectly applies the XOR logic. While a raw for loop is slightly faster in execution benchmarks, providing the .reduce() one-liner in an interview demonstrates strong mastery of modern functional language features.