Sponsored
Sponsored
This approach uses bit manipulation to solve the problem with constant space and linear runtime. The idea is to count the number of times each bit is set in the given numbers modulo 3 using two integers. This effectively filters out the bits that appear in numbers repeated thrice and leaves the bits of the unique number.
Time Complexity: O(n) - where n is the number of elements in the array.
Space Complexity: O(1) - as only a fixed amount of space is used regardless of the input size.
1def singleNumber(nums):
2 ones, twos = 0, 0
3 for num in nums:
4 twos = twos | (ones & num)
5 ones = ones ^ num
6 common = ones & twos
7 ones = ones & ~common
8 twos = twos & ~common
9 return ones
10
11nums = [0, 1, 0, 1, 0, 1, 99]
12print(singleNumber(nums))In Python, the problem is addressed with the same principle: ones and twos track the appearance of bits, and compatibility is ensured through logical operations to simulate three-bit counters for each position in the binary representation of numbers.
This approach involves using a data structure to count occurrences of each number. Although this uses linear time complexity, it requires additional memory to store frequencies, which violates the constant space constraint.
Time Complexity: O(n log n) - primarily due to the sorting step.
Space Complexity: O(1) - if in-place sort is assumed.
1#
This implementation sorts the array first, which costs O(n log n) time, and then iterates over it checking for numbers that do not repeat thrice by comparison. Although simple, this technique also requires modification of the input if sorting is destructive.