Algorithm
Problem Name: 137. Single Number II
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.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int singleNumber(int* nums, int numsSize) {
int i, ones, twos;
ones = twos = 0;
for (i = 0; i < numsSize; i ++) {
ones = (ones ^ nums[i]) & ~twos;
twos = (twos ^ nums[i]) & ~ones;
}
return ones;
}
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public int singleNumber(int[] nums) {
int seenOnce = 0;
int seenTwice = 0;
for (int num : nums) {
seenOnce = ~seenTwice & (seenOnce ^ num);
seenTwice = ~seenOnce & (seenTwice ^ num);
}
return seenOnce;
}
}
Copy The Code &
Try With Live Editor
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const singleNumber = function(nums) {
const hash = {}
nums.forEach(el => {
hash[el] = (hash[el] && hash[el] + 1) || 1
})
for(let el in hash) {
if(hash[el] === 1) return +el
}
};
Copy The Code &
Try With Live Editor
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return ((sum(set(nums)) * 3) - sum(nums)) // 2
Copy The Code &
Try With Live Editor
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0137_SingleNumberII
{
public int SingleNumber(int[] nums)
{
int seenOnce = 0, seenTwice = 0;
foreach (int num in nums)
{
seenOnce = ~seenTwice & (seenOnce ^ num);
seenTwice = ~seenOnce & (seenTwice ^ num);
}
return seenOnce;
}
}
}
Copy The Code &
Try With Live Editor
Input
Output