I don’t like this one. Let’s discuss two solutions:

Natural Solution

Here’s a natural-enough solution in Python. Observe how we use a “counter” object; that’s basically a hashmap, which is a fine-enough solution as well in my opinion. This is, in my opinion, the “right” solution.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counter = collections.Counter()
        for n in nums:
            counter[n] += 1
        for n in counter:
            if counter[n] == 1: return n
        # return None, assert. 

This is “inefficient”, in the sense that we’re using O(n) space and a bit more than O(n) time (I’m a pedant about hashmap time). However, it solves the general problem of “what’s the unique element in this sequence”. That problem isn’t super-common, but it’s not way-out-there.

Desired Solution

But! They want constant space and linear time. This is a nice enough “think outside the box” thing, but it’s so obviously fishing for a trick after-the-fact. It’s a tail-wagging-the-dog sort of situation, where someone obviously observed an interesting trick, and then constructed a question that can only be reasonably answered with that trick. What’s the trick? It involves XOR identities.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda a, b: a ^ b, nums)

Ooooh. The observation is that for XOR operation (the ^ operator):

• a^a = 0
• a^0 = a
• And everything commutes

So a sequence like a^a^b^b^c = c, because we end up with 0^0^c=c. That’s neat, but extremely dependent on the idea that the sequence contains an even number of every element, except one, which exists an odd number of times. I suppose it’s neat to keep the “flexibility” of thinking of array contents as values (as we do in the typical solution) and bit-sequences, but it’s really a fishing sort of question.

I’d do this for fun (I did do this for fun), but I’d suggest avoiding it except to show a neat consequence of XOR identities in a classroom. More bit manipulation questions here.