Single Number II

• leetcode 137
• medium

Description

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?

Hide Tags: Bit Manipulation

Hide Similar Problems: (M) Single Number (M) Single Number III

Thinking

Deriving the logic expression. I want to simulate a operation 0 - 1 - 2 - 0, So I need to two numbers to record the status. Write down the several probabilities.

Java Solution

public class Solution {
    public int singleNumber(int[] nums) {
        int one = 0, two = 0, temp;

        for(int i : nums){
            temp = ((~(one ^ two)) & i) | (one & (~i));
            two = (one & i)|(two & (~i));
            one = temp;
        }

        return one;
    }
}