Single Number II | Leetcode

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?

---

Solution: Count the number of one bits in the i-th bit position among all the numbers in the array (where i=0..31). If the count is not a multiple of 3, then set the i-th bit of the answer number as 1. When we have iterated from i=0 to i=31, then we would have obtained the complete answer number, so just return it.

Algorithm 1: Easy to Understand

public class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;
        for (int i = 0; i < 32; i++) {
            int bit = (1 << i);
            int bitCount = 0;
            for (int n: nums) {
                if ((n & bit) != 0) bitCount++;
            }
            if ((bitCount % 3) != 0) answer |= bit;
        }
        return answer;
    }
}

Algorithm 2: Probably No Need to Memorize (https://leetcode.com/discuss/43377/the-simplest-solution-ever-with-clear-explanation)

public class Solution {
    public int singleNumber(int[] nums) {
        int n0 = 0;
        int n1 = 0;
        for (int n: nums) {
            n0 = (n0 ^ n) & (~n1);
            n1 = (n1 ^ n) & (~n0);
        }
        return n0;
    }
}