Using digital logic design idea - counter to hack this type


  • 1
    //inspired by logical circuit design and boolean algebra;
    //counter - unit of 3;
    //current   incoming  next
    //a b            c    a b
    //0 0            0    0 0
    //0 1            0    0 1
    //1 0            0    1 0
    //0 0            1    0 1
    //0 1            1    1 0
    //1 0            1    0 0
    //a = a&~b&~c + ~a&b&c;
    //b = ~a&b&~c + ~a&~b&c;
    //return a|b since the single number can appear once or twice;
    class Solution {
    public:
        int singleNumber(vector<int>& nums) 
        {
            int t = 0, a = 0, b = 0;
            for(int i = 0; i < nums.size(); ++i)
            {
                t = (a&~b&~nums[i]) | (~a&b&nums[i]);
                b = (~a&b&~nums[i]) | (~a&~b&nums[i]);
                a = t;
            }
            return a | b;
        }
    };
    
    

    A very generalised solution is enclosed here - bit counting

    class Solution {
    public:
        int singleNumber(vector<int>& nums) 
        {
            int len = sizeof(int)*8, size = nums.size();
            int mask = 1, count = 0, ret = 0;
            for(int i = 0; i < len; ++i)
            {
                count = 0;
                for(int j = 0; j < size; ++j)
                    if(mask & nums[j]) count++;
                if(count % 3) ret |= mask;
                mask <<= 1;
            }
            return ret;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.