In this guide, you will get 137. Single Number II LeetCode Solution with the best time and space complexity. The solution to Single Number II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 nums appears exactly three times except for one element which appears once.
Complexity Analysis
Time Complexity: O(32n) = O(n)
Space Complexity: O(1)
137. Single Number II LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
137. Single Number II LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
137. Single Number II LeetCode Solution in Python
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 # code by PROGIEZ
