Leetcode and Lintcode

Single Number II

Problems:

Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.

Example
Given [1,1,2,3,3,3,2,2,4,1] return 4

Challenge
One-pass, constant extra space.

Leetcode link
Lintcode link

Solution:

This problem examines the ability of applying bit operation.
First, we create an integer array with size of 32, each int represent a bit of an integer.
Then for each bit position of an integer, we go through the input numbers, and accululate the value of the correpsonding bit.
As we know, the sum of each bit shold be dividable by 3 except one number.
So we mod 3 for each bit, then the left number is the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*************************************************************************
    > File Name: SingleNumberII.java
    > Author: Yao Zhang   
    > Mail: psyyz10@163.com 
    > Created Time: Sun 15 Nov 23:40:03 2015
 ************************************************************************/
                             
public class SingleNumberII{
    public int singleNumber(int[] nums){
        int result = 0;   
        int[] bits = new int[32];
                             
        for (int i = 0; i < bits.length; i++){
            for (int j = 0; j < nums.length; j++){
                bits[i] += (nums[j] >> i) & 1;
                bits[i] %= 3;
            }                
                             
            result |= bits[i] << i;                                                                                                                                                  
        }                    
                             
        return result;       
    }                        
}