Description
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,3,2] Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99] Output: 99
Constraints:
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1- Each element in
numsappears exactly three times except for one element which appears once.
Solution
Python3
class Solution:
def singleNumber(self, nums: List[int]) -> int:
bits = [0] * 32
for x in nums:
for i in range(32):
if (x >> i) & 1 == 1:
bits[i] += 1
bits[i] %= 3
res = 0
for i in range(32):
if bits[i]:
res |= (1 << i)
if res & 1 << 31:
res -= 2 ** 32
return res