137.Single Number II

Tags: [bit], [bit_shift], [bit_manipulation], [math]

Com: {t}, {t_review}

Hard: [##]

Link: https://leetcode.com/problems/single-number-ii/\#/description

Given an array of integers, every element appearsthreetimes except for one, which appears exactly once. Find that single one.

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

Solution: Math, Bit, Bit Manipulation

public class Solution {
    public int singleNumber(int[] nums) {
        if (nums.length == 0) {
            return -1;
        }

        int result = 0;
        int sum = 0;
        for (int i = 0; i < 32; i ++) {
            sum = 0;
            for (int num: nums) {
                sum += (num >> i) & 1;
            }

            result += (sum % 3) << i;
        }

        return result;
    }
}

Revelation:

• If we look at bit by bit, and assume there are 32 bits in one integer, and we look the bit of num column by column. If we see one column, because all num appear three times, except one, so if we sum all bits from all numbers for one column should be something like: 1 + 1 + 1 + 0 + 0 + 0 + 1 = 4, 4 % 3 = 1, so the 'special' num's bit at this column is '1'. Another example, 1 + 1 + 1 + 0 + 0 + 0 + 0 = 3, 3 % 3 = 0, so the 'special' num's bit at this column is '0'.

Note:

• Time complexity = O(n), n is the number of elements in the given nums.
• Space complexity = O(1).