« Back
in Leetcode Java Bit Manipulation read.

Leetcode 137 Single Number II.

Problem 137 Single Number II

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?

If you have never seen this kind of problem, that would be really hard to solve. But if you have done this before, not a big deal.

And the Bit Manipulation problems are very common in Leetcode.

public class Solution {
    public int singleNumber(int[] nums) {
        int ones=0,twos=0,threes=0;
        for(int i=0 ;i< nums.length; i++){
            twos=(ones&nums[i])|twos;
            ones=nums[i]^ones;
            threes=~(ones&twos);
            ones=threes&ones;
            twos=threes&twos;
        }
        return ones;
    }
}
comments powered by Disqus