Challenge me , thx


  • 550
    A
    public int singleNumber(int[] A) {
        int ones = 0, twos = 0;
        for(int i = 0; i < A.length; i++){
            ones = (ones ^ A[i]) & ~twos;
            twos = (twos ^ A[i]) & ~ones;
        }
        return ones;
    }

  • 0
    E
    This post is deleted!

  • 1
    G

    fellow, what do u mean by 'GDS' ?


  • 1
    H

    This solution is awesome !


  • 10
    S

    Thanks for that, I thought there was a solution along those lines but couldn't think of it.

    As for challenging you:

    1. Does this work when the number that doesn't occur exactly three times occurs more than once? If it appears twice, or four times, and so on.

    2. This works when all but one value appear three times, can you extend it to 4? 5? Can you generalize it to take the number of repetitions as a parameter?


  • 67
    L

    Beautiful. Let me describe it to see if I'm understanding it right:

    First time number appear -> save it in "ones"

    Second time -> clear "ones" but save it in "twos" for later check

    Third time -> try to save in "ones" but value saved in "twos" clear it.


  • 12
    N

    This solution is awesome. And it can easily be extended to 4,5,6...
    The core idea is as follows. For one element x occurring P+1 times, we use P intermediate values, M[P].

    For these intermediate values, we want to construct a loop.
    [0,0,...0] ----> [0,x,...0] ----> [0,0,x...0] ... [0,0,...x] ----> [0,0,...x]. This can be achieved by following codes.
    for(int j=0;j<P;j++)
    {
    int tmp = -1;
    for(int k=0;k<P;k++)
    {
    if(k!=j)
    {
    tmp &= ~M[k];
    }
    }
    M[j] = (x^M[j]) & tmp;
    }


  • 0
    Z

    You got it right. Also it won't be saved in "twos", as A[i] itself clears it.


  • 0
    J

    Can you explain more details please? I can't understand how did you come up with this solution.


  • -2
    D
    This post is deleted!

  • -153
    M

    umm your algorthm doesn't work?

    Try A = { 3, 3, 1}

    i=0:
    A[i] = 3 = 0011, ones = 0011, twos = 0000

    i=1:
    A[i] = 3 = 0011, ones = 0000, twos = 0011

    i=2
    A[i] = 1 = 0001, ones = (0000 ^ 0001) & ~0011 = 0001 & 1100 = 0000

    challenged, thx.


  • 0
    Z

    @againest1, could you please explain more how this works: ones = (ones ^ A[i]) & ~twos? Thanks!


  • 0
    O

    for 1)

    return one ^ two; //although it still doesn't work for six times and so on


  • 1
    J

    no value appears 3 times in your array..


  • -3
    M

    ones and twos are extra space or not???


  • -2
    Y

    Beautiful solution but failed for this test case: int [] A = {1,1,1,5,5,5,5,5,5}; the output from your solution is 0, though the correct output should be 5.


  • 621
    W

    The code seems tricky and hard to understand at first glance.
    However, if you consider the problem in Boolean algebra form, everything becomes clear.

    What we need to do is to store the number of '1's of every bit. Since each of the 32 bits follow the same rules, we just need to consider 1 bit. We know a number appears 3 times at most, so we need 2 bits to store that. Now we have 4 state, 00, 01, 10 and 11, but we only need 3 of them.

    In this solution, 00, 01 and 10 are chosen. Let 'ones' represents the first bit, 'twos' represents the second bit. Then we need to set rules for 'ones' and 'twos' so that they act as we hopes. The complete loop is 00->10->01->00(0->1->2->3/0).

    • For 'ones', we can get 'ones = ones ^ A[i]; if (twos == 1) then ones = 0', that can be tansformed to 'ones = (ones ^ A[i]) & ~twos'.

    • Similarly, for 'twos', we can get 'twos = twos ^ A[i]; if (ones* == 1) then twos = 0' and 'twos = (twos ^ A[i]) & ~ones'. Notice that 'ones*' is the value of 'ones' after calculation, that is why twos is
      calculated later.


    Here is another example. If a number appears 5 times at most, we can write a program using the same method. Now we need 3 bits and the loop is 000->100->010->110->001. The code looks like this:

    int singleNumber(int A[], int n) {
    	int na = 0, nb = 0, nc = 0;
    	for(int i = 0; i < n; i++){
    		nb = nb ^ (A[i] & na);
    		na = (na ^ A[i]) & ~nc;
    		nc = nc ^ (A[i] & ~na & ~nb);
    	}
    	return na & ~nb & ~nc;
    }
    

    Or even like this:

    int singleNumber(int A[], int n) {
    	int twos = 0xffffffff, threes = 0xffffffff, ones = 0;
    	for(int i = 0; i < n; i++){
    		threes = threes ^ (A[i] & twos);
    		twos = (twos ^ A[i]) & ~ones;
    		ones = ones ^ (A[i] & ~twos & ~threes);
    	}
    	return ones;
    }
    

    I hope all these above can help you have a better understand of this problem.


  • 2
    C

    Great, ones and twos just work as the count of corresponding bits of 1. (ones, twos) can be 00, 01 and 10. For special case (1,0), if there is an extra 1, it will be reset to (0,0).

    If one bit of ones is 1. it indicates that the bit has 3*n+1 1s.


  • 0
    H
    This post is deleted!

  • 0
    S
    This post is deleted!

Log in to reply
 

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