Problem Link - Bit Manipulation - Single Number
Problem Statement
You are given an array A_1, A_2, \dots, A_N of length N. Each distinct element appears twice except for one. Find that single one.
Approach
The code uses the XOR operation to identify the unique element in the array, leveraging these key properties:
- XOR of a number with itself is 0: x⊕x=0.
- XOR of a number with 0 is the number itself: x⊕0=x.
- XOR is commutative and associative: The order does not affect the result.
By XORing all elements, pairs cancel each other out, leaving only the unique element.
Time Complexity
O(N) - where N is the number of elements in the array.
Space Complexity
O(1) - since we are using a constant amount of extra space.