2

This is a leetcode question I just saw. The solution someone gave is a bit hard to understand, I'm hoping someone can elaborate a bit:

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Do this in linear time with no extra space.

The solution someone gave:

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;
}

This seems like an awesome solution, but It's a bit hard to understand. Someone in the comments said this could be extended to any number of repeats.

Improve this question
2
  • 1
    If every element appears twice except for one once then you could just xor all the numbers. I suppose this is the adaptation for 3 times. Commented May 21, 2017 at 19:14
  • Using the array [n, n, n], it can be see that the variables take on the values n, 0, 0, n, and 0, 0. Now just show that the order of the array does not matter. Commented May 21, 2017 at 19:27

1 Answer 1

Reset to default
3

Suppose for each of the bits in an int, you have a counter. That counter can take the values 0, 1, or 2. For each 1 bit in an input number, you increment the corresponding counter, looping back to 0 when you would hit 3.

If a number appears 3 times in the array, the counters corresponding to its 1 bits will be incremented 3 times for that number, ultimately having no effect. The number that appears once will have its corresponding counters incremented once, so at the end, the counters will reflect only the 1 bits of the number that appears once.

This is basically a ternary version of the "XOR everything" solution you would use if the repeated numbers appeared 2 times instead of 3. We could go a little further with the ternary and use the base 3 digits of the input instead of the bits, but bits are easier to work with.

The ones and twos variables are used to maintain these counters. A 1 bit in the ones variable corresponds to a counter value of 1, and a 1 bit in the twos variable corresponds to a counter value of 2. A counter value of 0 corresponds to 0 bits in both ones and twos.

This:

ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;

is a counter update. Look at it on a bit-by-bit basis.

If a bit is set to 0 in A[i], then these lines don't affect that bit in ones and twos.

If a bit is set to 1 in A[i], then

  • if that bit is set in ones, it's unset in ones (because of the ^ A[i]) and set in twos (because of the ^ A[i], and then & ~ones doesn't unset it because we just unset the bit in ones).
  • if that bit is set in twos, it remains unset in ones (because of the & ~twos) and gets unset in twos (because of the ^ A[i]).
  • if that bit was unset in both ones and twos, it gets set in ones (because of the ^ A[i]) and remains unset in twos (because of the & ~ones).

At the end, ones has its bits set corresponding to the element of A that only appeared once, so we return ones.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

thats a great way to look at it. Thanks for the explanation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.