LeetCode #136. Single Number

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.

---

Using XOR:
* All duplicate elements cancel themselves out: a ^ a = 0
* The remaining number: 0 ^ single = single

Time Complexity: O(n)

Single pass through the array → O(n)

Space Complexity: O(1)

Uses only one integer (result) → O(1)

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= nums[i]; 
        }
        return result;
    }
}