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
numsappears 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;
}
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;
}
}
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
}
};
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
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;
}
}
}
Input
Output