Sponsored
Sponsored
The idea is to use the XOR operation to find two unique numbers that appear only once in the array. This can be achieved by:
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), constant space is used for variables non-dependent on input size.
1def singleNumber(nums):
2 xorAll = 0
3 for num in nums:
4 xorAll ^= num
5
6 diffBit = xorAll & (-xorAll)
7 x = 0
8 y = 0
9 for num in nums:
10 if num & diffBit:
11 x ^= num
12 else:
13 y ^= num
14 return [x, y]
15
16nums = [1, 2, 1, 3, 2, 5]
17result = singleNumber(nums)
18print("Single numbers are:", result)The Python implementation is straightforward with the use of bitwise operations for efficient computation, following the same XOR-based partitioning strategy.
An alternative approach that utilizes hash maps to count occurrences of each element would typically find the unique numbers. Although this solution is more straightforward, it requires additional space and does not strictly meet the problem constraints of constant extra space.
Time Complexity: O(n), for passing through the array for counting.
Space Complexity: O(n), as space is allocated for counts of numbers.
1from collections import Counter
2
3def singleNumber(nums):
4 count
This Python solution leverages collections.Counter to track occurrences and quickly find numbers appearing only once. While simple, it utilizes additional space beyond the constraints of the problem for learning purposes.