Bit Manipulation - 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 linear runtime complexity and use only constant extra space.

Input: nums = [2, 2, 1]
Output: 1
Explanation: 1 appears only once, while 2 appears twice.

Input: nums = [4, 1, 2, 1, 2]
Output: 4
Explanation: 4 appears only once; 1 and 2 each appear twice.

The key insight is the XOR property: a ^ a = 0 and a ^ 0 = a. XOR-ing all numbers together cancels out pairs, leaving only the single number.

Initialize result to 0.
XOR every number in the array with the result.
Since duplicate numbers cancel out (x ^ x = 0), only the unique number remains.

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

Complexity Analysis:

Time complexity: O(n) — single pass through the array.
Space complexity: O(1) — only one variable used.