Sunday, January 11, 2015

LeetCode 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?
public class Solution {
    public int singleNumber(int[] A) {
        // one: The bits that have appeared 1st time or 4th time or 7th time .. etc.
        // two: The bits that have appeared 2nd time or 5th time or 8th time .. etc.
        int one = 0, two = 0, three = 0;
 
        // Let us take the example of {3, 3, 2, 3} to understand this
        for (int i = 0; i < A.length; i++)
        {
            /* The expression "one & A[i]" gives the bits that are
            there in both 'one' and new element from A. We
            add these bits to 'two' using bitwise OR
            Value of 'two' will be set as 0, 3, 3 and 1 after 1st,
            2nd, 3rd and 4th iterations respectively */
            two  = two | (one & A[i]);
 
            /* XOR the new bits with previous 'one' to get all bits
            appearing odd number of times
            Value of 'one' will be set as 3, 0, 2 and 3 after 1st,
            2nd, 3rd and 4th iterations respectively */
            one  = one ^ A[i];
 
            /* The common bits are those bits which appear third time
            So these bits should not be there in both 'one' and 'two'.
            'three' contains all these bits that appear third time
            Value of 'three' will be set as 00, 00, 10 and 01
            after 1st, 2nd, 3rd and 4th iterations respectively */
            three = one & two;

            /* Remove common bits (the bits that appear third time) from 'one'
            Value of 'one' will be set as 3, 0, 0 and 2 after 1st,
            2nd, 3rd and 4th iterations respectively */
            one = one & (~three);

            /* Remove common bits (the bits that appear third time) from 'two'
            Value of 'two' will be set as 0, 3, 1 and 0 after 1st,
            2nd, 3rd and 4th itearations respectively */
            two = two & (~three);        
        }
        
        return one;
    }
}

No comments:

Post a Comment