CODEWITHSUNDEEP
algorithm
bli00
bli00

Reputation: 2787

Algorithm: Find single number in array

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.

Upvotes: 2

Views: 1331

Answers (1)

user2357112
user2357112

Reputation: 280291

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.

Upvotes: 3

Related Questions