LeetCode Q137: Single Number II

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

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:

The key is to look at the number of 1's showing up at each bit of 32 bits of an integer. Since all numbers except one show up exact three times. So, the bits which are not multiple of 3 are bits belonging to the target single number. Same idea thus can be applied to problem in which all number except one show up exact K times.