Leetcode: Single Number II

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

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

Understand the problem:
The problem is similar to the Single Number I, except that each number appears three times. Note that the problem asks for linear time complexity and constant space. 

Naive Solution:
The naive solution could use a hash table. It uses hash table instead of hash set because we want store the number of occurrence of each number. For each number if it is the first or second occurrences, we update the second value. For the third times, we remove that entry. So the only number in hash table is the one we are looking for.

Code (Java):

public class Solution {
    public int singleNumber(int[] A) {
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        int num = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (!hashMap.containsKey(A[i])) {
                hashMap.put(A[i], 1);
            } else if (hashMap.get(A[i]) == 1) {
                hashMap.put(A[i], 2);
            } else if (hashMap.get(A[i]) == 2) {
                hashMap.remove(A[i]);
            }
        }
        Set<Integer> set = new HashSet<Integer>();
        set = hashMap.keySet();
        
        for (Integer n : set) {
            num = n;
        }
        return num;
    }
}

  
Discussion:
We see that the solution has O(n) in time, however O(n) in space. So we need to find out another way to solve it using constant space.

A Better Solution:

public class Solution {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int[] bits = new int[32];
        
        // step 1: calcuate the number of bits for each number
        for (int num : nums) {
            int mask = 1;
            for (int i = 31; i >= 0; i--) {
                if ((num & mask) != 0) {
                    bits[i]++;
                }
                mask = (mask << 1);
            }
        }
        
        // step 2: find out the single number
        int result = 0;
        for (int i = 0; i < 32; i++) {
            bits[i] %= 3;
            if (bits[i] == 1) {
                result += 1;
            }
            
            if (i == 31) {
                break;
            }
            
            result = (result << 1);
        }
        
        return result;
    }
}