Single Number I

Problem Link

Problem Statement

Given a non-empty array of integers nums, every element appears twice except for one.
Find and return that single one.

You must implement a solution with linear runtime complexity and use only constant extra space.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

Constraints

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
Each element appears exactly twice except for one

Intuition

XOR (^) is a powerful operation for this problem because:

x ^ x = 0 → any number XOR itself is 0
x ^ 0 = x → any number XOR 0 is itself
XOR is commutative and associative, so order doesn’t matter

By XORing all elements together, the pairs cancel out, and only the unique number remains.

Approach: XOR All Elements

Initialize a variable xor = 0
Traverse the array, XOR each element with xor
After the loop, xor will hold the single number

Java Code

class Solution {
    public int singleNumber(int[] nums) {
        int xor = 0;
        for (int i : nums) {
            xor ^= i;
        }
        return xor;
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	O(n)
Space Complexity	O(1)
Explanation	Single pass, no extra space used beyond a variable

Dry Run

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

Initial xor = 0
Step-by-step:
- xor ^= 4 → xor = 4
- xor ^= 1 → xor = 5
- xor ^= 2 → xor = 7
- xor ^= 1 → xor = 6
- xor ^= 2 → xor = 4

Result: 4

Conclusion

This problem demonstrates an elegant use of bitwise XOR for eliminating duplicates. It's a classic example of:

Constant space optimization
Using mathematical properties of XOR
Efficient linear-time solution