Our blog, keeping you up-to-date on our latest news.

 

[Leetcode]Single Number II

January 29, 2015 at 6:41 am | Algorithms | No comment

 

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?

[Thoughts]

This one is similar to the “Single Number”, and the idea is the same too, try to make the numbers appear three times to zero, and then leave the single one as our result.
One way is to look into each integer in a bit way. then each number is 32 bits. if the number appears three times, that means each bit for this number appears three times as well. then if we add each bit accordingly, and then use math mod(“%”) operation, all numbers appear three times will be 0.
And this way is very common, it could apply to element appear twice, three times, four times etc.

Solution

public class Solution {
    public int singleNumber(int[] A) {
 
        int result = 0;
 
        for(int i = 0; i< 32; i++){
            int count = 0;
            for(int j=0; j<A.length; j++){
                //add up all number's 'ith' bits.
                count+=((A[j]>>i)&1);
            }
            result|=((count%3)<<i);
        }
        return result;
    }
}

<< Back to Blog Discuss this post

 
Comments are closed.