One line more code to distinguish [1,1,1,2,2] and [1,1,1,2]?


  • 3
    C

    I think this problem is a little unclear. In my point of view, the single one can be:

    (1) the one which has different numbers than others. Can have 1 or 2 but not 3 numbers.

    (2) the one which appears only once.

    Which one is correct?

    So we should consider about it when we are in the interview. The following code can solve the (1) case by adding one more line checking, instead of return result directly.

    public int singleNumber(int[] nums) {
        int res=0;
        for(int i=0;i<32;i++){
            int count = 0;
            for(int j=0;j<nums.length;j++){
                count+=(nums[j]>>i)&1;
            }
            res|=(count%3)<<i;
        }
        /*
         *here solve 1,1,1,2,2 and 1,1,1,2 cases
         */
        if(nums.length%3==2) return res/2;
        else return res;
    }
    

    P.S.: if (1) is correct, in fact, it can also has 4,5..., but not 3 numbers. So this is not a porper assumption, because we cannot handle all these cases.


  • 0
    D

    Here is my python code, basically same as girikuncoro's solution, but I also thought it needed to cover the cases where the number comes up once or twice. Pretty much if your count modulo 3 is non-zero, you want to have a 1 in that position.

    def singleNumber(self, nums):
        number = 0
        for i in range(32):
            count = 0
            for num in nums:
                count += (num >> i) & 1
            remainder = count % 3
            if i == 31 and remainder:
                number -= 1<<i
            elif remainder:
                number |= 1 << i
        return number
    

Log in to reply
 

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