Question

Formatted question description: https://leetcode.ca/all/137.html

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 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Algorithm

A 32-bit number can be created to count the number of occurrences of 1 in each digit.

If a certain digit is 1, then if the integer appears three times, the remainder of 3 is 0, so that the numbers of each digit position are added up then take the remainder of 3, and the final number remaining is a single number.

Code

public class Single_Number_II {

    public class Solution {
        public int singleNumber(int[] nums) {

            if (nums == null || nums.length == 0) {
                return 0;
            }

            // first doubt, how long bits should I check.
            // int is 32 bit, so bitmap length is 32
            int single = 0;
            for (int bitPos = 0; bitPos < 32; bitPos++) {
                int sumAtThisPos = 0;

                for (int j = 0; j < nums.length; j++) {
                    int digitInA = ((nums[j] >> bitPos) & 1);
                    sumAtThisPos += digitInA;
                }

                int afterMod = sumAtThisPos % 3;
                single |= (afterMod << bitPos);
            }

            return single;
        }
    }
}

############

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int cnt = 0;
            for (int num : nums) {
                cnt += num >> i & 1;
            }
            cnt %= 3;
            ans |= cnt << i;
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/single-number-ii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unsigned ans = 0;
        for (int i = 0; i < 32; ++i) {
            int cnt = 0;
            for (unsigned n : nums) {
                cnt = (cnt + ((n >> i) & 1)) % 3;
            }
            ans |= cnt << i;
        }
        return ans;
    }
};

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            cnt = sum(num >> i & 1 for num in nums)
            if cnt % 3:
                if i == 31: # int overflow， or just throw exception
                    ans -= 1 << i
                else:
                    ans |= 1 << i
        return ans

############

class Solution(object):
  def singleNumber(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    def singleNumberK(nums, k):
      ret = 0
      count = [0] * 32
      for i in range(0, 32):
        for num in nums:
          if num & (1 << i):
            count[i] += 1
        if count[i] % 3 != 0:
          ret |= 1 << i
      if ret > 0x7fffffff:
        ret -= 0x100000000
      return ret

    return singleNumberK(nums, 3)

func singleNumber(nums []int) int {
	ans := int32(0)
	for i := 0; i < 32; i++ {
		cnt := int32(0)
		for _, num := range nums {
			cnt += int32(num) >> i & 1
		}
		cnt %= 3
		ans |= cnt << i
	}
	return int(ans)
}

function singleNumber(nums: number[]): number {
    let ans = 0;
    for (let i = 0; i < 32; i++) {
        const count = nums.reduce((r, v) => r + ((v >> i) & 1), 0);
        ans |= count % 3 << i;
    }
    return ans;
}

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        for i in 0..32 {
            let count = nums.iter().map(|v| v >> i & 1).sum::<i32>();
            ans |= count % 3 << i;
        }
        ans
    }
}

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var a = nums.sorted()
        var n = a.count
        for i in stride(from: 0, through: n - 2, by: 3) {
            if a[i] != a[i + 1] {
                return a[i]
            }
        }
        return a[n - 1]
    }
}

137 - Single Number II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions