Day 22: Single Number II
You are given an array of integers. Every element in the array appears three times, except for one, which appears only once. Return that element.
(This is really straightforward if you use a hashmap and just count the elements, but we can also do this in linear time with constant extra memory)
This is a twist on a classic parity problem. If you want to eliminate elements which occur twice, you can just XOR them together. In principle, there's some forms of XOR gates that work with 3 inputs at once, but I can't figure out how I'd iterate over the elements.
After a bit of Binging around, I found the obvious solution: just count parity. Since we need to do this in constant space, I thought about ways to encode that succinctly. In the XOR method, we're counting parity of bits. We can do that in sizeof(int) space with an array!
Once we have the parity, we can combine all the bits which show up with a parity that isn't a multiple of 3.
I have a few more days to catch up on. All the really interesting problems take more time.