Given an integer array nums where every element appears exactly three times except for one element which appears exactly once. Find the single element and return it. You must implement a solution with linear runtime and constant extra space.
nums = [2,2,3,2]3nums = [0,1,0,1,0,1,99]99By summing the bits of all numbers at each position, we count how many times each bit appears. Since every other number appears exactly 3 times, their bits contribute a multiple of 3 to the counters. Taking the modulo 3 of each counter effectively cancels out the numbers that appear 3 times, leaving only the bits of the single number!
XOR does not work here, because three copies do not cancel. A hash map works, but it uses extra space.
Look at each bit position separately. Count how many numbers have a 1 in that position. Numbers appearing three times add a multiple of 3 to that count. So the count mod 3 is exactly the bit of the single number.
Count bits per position, mod the repeat count. The same trick works for any repeat count k.
Run the animation above on your own input, or watch the 1:22 video explanation of Single Number II with a dry run and Java code.