Another bitwise operation method for single numbers, with detailed explanation


  • 9
    H

    I think my solution is easier to understand.

    First, here is my code for Single Number II

    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0 , threes = 0;
        for(int x:nums){
            threes = twos&x;
            twos = (ones&x|twos) & (~threes);
            ones = (ones|x)&(~threes);
        }
        return ones;
    }
    

    Run a loop for all elements in array. At the end of every iteration, maintain following three values.

    threes: The bits that have appeared 3st time or 6th time or 9th time .. etc [times % 3 == 0 && times > 1].

    twos: The bits that have appeared 2nd time or 5th time or 8th time .. etc. [times % 3 >= 2 && times%3 != 0, here so times%3 == 2]

    ones: The bits that have appeared 1nd/2nd time or 4th/5th time or 7th/8th time .. etc. [times %3 >=1 && time %3 != 0, here (times %3 ==1 or times %3 == 2)]

    each iteration, when x comes

    cause pre twos is (times%3 == 2), then now threes = twos&x;

    to calculate twos, first we get the bits satify times % 3 >= 2 , it's (ones&x|twos), then get rid of the bits that times%3 == 2 namely threes, then twos = (ones&x|twos) & (~threes);

    to calculate ones, first we get the bits satify times % 3 >= 1, it may come from pre ones or new comer x, so it's (ones|x) , also we need to get rid of the bits that times%3 == 2 namely threes, then ones = (ones|x)&(~threes);

    sorry for my English.

    ===============================================================================

    for this problem,

    Statement of our problem: "Given an array of integers, every element appears k (k >1) times except for one, which appears p times(p>=1, p % k != 0). Find that single one."

    public int singleNumber(int[] nums) {
        int ks = 0, k_1s = 0 ... ps=0, ... ones = 0;
        for(int x:nums){
            ks = k_1s&x;
            k_1s = (k_2s&x|k_1s) & (~ks);
            k_2s = (k_3s&x|k_2s) & (~ks);
            .......
            twos = (ones&x|twos) & (~ks);
            ones = (ones|x)&(~ks);
        }
        return ps;
    }

  • 0

    Looks like a great solution, but the explanation is seriously broken. Like, you explain the meaning of "ones" twice and don't explain the meaning of "twos", and the two "ones" descriptions look too similar for one to be "twos". And you explain the calculation of "twos" twice and don't explain the calculation of "ones".


  • 0
    H

    Has been corrected, thank you for pointed it out.


Log in to reply
 

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