[LeetCode] Problem 137 - Single Number II

Posted on | In ,

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

No.1

Input: [2,2,3,2]

Output: 3

No.2

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

Output: 99

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int singleNumber(int[] nums) {
    int num = 0;

    for (int i = 0; i < 32; i++) {
        int sum = 0;

        for (int j = 0; j < nums.length; j++) {
            if (((nums[j] >> i) & 1) == 1)
                sum++;
        }

        num |= (sum % 3) << i;
    }

    return num;
}

Improvement

  1. A new number appears - It gets XOR’d to the variable “ones”.
  2. A number gets repeated(appears twice) - It is removed from “ones” and XOR’d to the variable “twos”.
  3. A number appears for the third time - It gets removed from both “ones” and “twos”.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int singleNumber(int[] nums) {
    int once = 0;
    int twice = 0;
    int common;

    for (int i = 0; i < nums.length; i++) {
        twice |= once & nums[i];
        once ^= nums[i];
        common = ~(once & twice);
        once &= common;
        twice &= common;
    }

    return once;
}