[LeetCode] 137. Single Number II

Posted on | In

Problem

Given a non-empty array of integers, every element appears three times 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?

Example 1:

1
2
Input: [2,2,3,2]
Output: 3

Example 2:

1
2
Input: [0,1,0,1,0,1,99]
Output: 99

Explanation

  1. We need to think of some method to make some binary numbers reset to zero after three changes. We can use two binary number 00, when facing three times of the same number, it should reset back to 00, 00->01->10->00.

    1
    2
    3
                 00 (+) 1 = 01
             01 (+) 1 = 10
             10 (+) 1 = 00 ( mod 3)

  2. Init a b are zeros, r is our number. From the above example, a is the left 0, b is the right 0 initially. For example, a b are both zero, when we hit the 1 the first time, then b is updated to 1, a is still 0, which is 01. When we hit the 1 the second time, then ab is 10. When we hit the 1 the third time, then ab reset to 00. We know that there is one number only appears once, so the result should stored in b. The formula for updating both a and b when facing one number is below:

    1
    2
                 b = b xor r & ~a;
             a = a xor r & ~b;

Solution

1
2
3
4
5
6
7
8
9
10
class Solution {
   public int singleNumber(int[] nums) {
       int a = 0, b = 0;
       for (int i = 0; i < nums.length; i++) {
           b = (b ^ nums[i]) & ~a;
           a = (a ^ nums[i]) & ~b;
       }
       return b;
   }
}