LeetCode Solutions
137. Single Number II
Time: $O(32n) = O(n)$ Space: $O(1)$
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int sum = 0;
for (const int num : nums)
sum += num >> i & 1;
sum %= 3;
ans |= sum << i;
}
return ans;
}
};
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int sum = 0;
for (final int num : nums)
sum += num >> i & 1;
sum %= 3;
ans |= sum << i;
}
return ans;
}
}
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ones = 0
twos = 0
for num in nums:
ones ^= num & ~twos
twos ^= num & ~ones
return ones