Why it works
- Look at one bit position. Each number that occurs three times puts 0 or 3 ones there, so the triples give a multiple of 3. The single number adds 1 or 0 on top, and ones % 3 tells which.
- Bits do not mix: each position is counted on its own, and the positions with ones % 3 = 1 are exactly the 1 bits of the answer. In column 0 the two triples give 6 ones, and 6 % 3 = 0.
- Plain xor does not work here: three copies of a number flip its bits three times and leave one copy. Here xor of everything is 0, not 6.
Complexity
Time O(w · n), where w is the width: one pass over the numbers per bit, and w = 32 on LeetCode, so O(n). Memory O(1): the count and the answer.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗