Question

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

137	Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99


Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

@tag-bit

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

Java

  • 
    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;
            }
        }
    }
    
  • // 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(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)
    
    

All Problems

All Solutions