Sponsored
Sponsored
This approach leverages the properties of XOR bitwise operation. The XOR of a number with itself is 0, and the XOR of a number with 0 is the number itself. Thus, XORing all elements in the array results in getting the single number because all other numbers cancel themselves out.
Time Complexity: O(n) - We go through the array once.
Space Complexity: O(1) - We only use a single integer to store the result.
1def singleNumber(nums):
2 result = 0
3 for num in nums:
4 result ^= num
5 return result
6
7nums = [2, 2, 1]
8print(singleNumber(nums)) # Output: 1The singleNumber function iteratively applies the XOR operation on the list of numbers. The duplicates nullify themselves leaving the single number.
In this approach, we use a hash map (or dictionary) to count occurrences of each number. The single number will have a count of 1. This isn't the optimal solution in terms of extra space but is valid if space was not constrained.
Time Complexity: O(n) - We traverse the array twice (once for filling the map, once for checking the counts).
Space Complexity: O(n) - Extra space proportional to the input range.
1
The JavaScript function uses an object as a map to count each number, returning the number that appears only once.