https://leetcode.com/problems/single-number-ii

There are several 'magical' solutions for this problem I saw in comments, done in O(n), which I really enjoed to read, however I doubt if you never saw this problem you can suceed in real interview. That is why I suggest maybe not the fastest, but much more easier to come up solution. The idea is similar to problem Single Number, but here we need to count each bit modulo 3. So, we

  1. Iterate over all possible 32 bits and for each num check if this num has non-zero bit on position i with num & (1<<i) == (1<<i) formula.
  2. We evaluate this sum modulo 3. Note, that in the end for each bit we can have either 0 or 1 and never 2.
  3. Next, update our answer single with evaluated bit.
  4. Finally, we need to deal with overflow cases in python: maximum value for int32 is 2^31 - 1, so if we get number more than this value we have negative answer in fact.

Complexity: time complexity is O(32n), which may be not fully honest linear, but is fine for the purpose of this problem. If we want just O(n) complexity, I think problem becomes not medium but hard. Space complexity here is O(1).

class Solution:
    def singleNumber(self, nums):
        single = 0
        for i in range(32):
            count = 0
            for num in nums:
                if num & (1<<i) == (1<<i): count += 1
            single |= (count%3) << i
            
        return single if single < (1<<31) else single - (1<<32)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0137