Single Number II

leetcode 137.

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

Solution. For example, if the numbers are [5, 5, 5, 2, 2, 2, 3]. We count the sum of 1 in each bit among these number. If the sum % 3 == 0, it means the answer should be 0 for this bit. Or it should be 1.

I don’t quite understand the best solution in discussion. But I think this solution is durable and easy to understand.

public static int singleNumber(int[] nums) {
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        int sum = 0, bit = 1 << i, base = 1 << i;
        for (int j = 0; j < nums.length; j++) {
            if ((nums[j] & bit) != 0) {
                sum++;
            }
        }
        if (sum % 3 != 0) {
            ans = ans | base;
        }
    }
    return ans;
}

Check my code on github.