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

x
+
cmd
nums = [2,2,3,2]

Output

x
+
cmd
3

#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

x
+
cmd
nums = [2,2,3,2]

Output

x
+
cmd
3

#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

x
+
cmd
nums = [0,1,0,1,0,1,99]

Output

x
+
cmd
99

#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

x
+
cmd
nums = [0,1,0,1,0,1,99]

Output

x
+
cmd
99

#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

x
+
cmd
nums = [2,2,3,2]

Output

x
+
cmd
3
Advertisements

Demonstration


Previous
#136 Leetcode Single Number Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#138 Leetcode Copy List with Random Pointer Solution in C, C++, Java, JavaScript, Python, C# Leetcode