A Bit of Ancient Algorithmic Magic, or Solving an Intriguing Sequence of Tasks From LeetCode

Some time ago, I came across an amusing series of tasks on the website leetcode.com. The tasks themselves are not too difficult, but their solutions are quite intriguing. Moreover, problems of this type often appear in interviews at major companies, and understanding the methods of their solution can be quite beneficial.

The First Task Is 136. Single Number (Easy)

Given a non-empty array of integers where every element appears twice except for one, you need to find the element without a pair. Solve the problem in O(n) time complexity and with constant extra memory.

Example 1:

Input: nums = [1, 3, 3, 2, 6, 2, 1]

Output: 6

Example 2:

Input: nums = [12, 1, 1, 7, 1, 12, 1]

Output: 7

Example 3:

Input: nums = [6]

Output: 6

We will leverage the XOR function property, which yields 1 only when its operands are different. By traversing through all the elements of the array and performing bitwise XOR on them, we will zero out all identical bit values. As a result, what remains will be the desired outcome.

Here is a short Python3 solution code:

def single_number(nums: list) -> int:
    result = 0

    for el in nums:
        result ^= el

    return result

We use only as much additional memory as an integer occupies, and find the solution in a single pass through the given array, giving us O(n) complexity. This is a concise and elegant solution.

The Second Problem Is 137. Single Number II (Medium Difficulty)

Given a non-empty array of integers where every element appears three times except for one, and only one element appears once, we need to find this unique element. Solve the problem in O(n) time complexity and with constant extra memory.

Example 1:

Input: nums = [3, 1, 3, 3]

Output: 1

Example 2:

Input: nums = [12, 1, 1, 5, 1, 12, 12]

Output: 5

Example 3:

Input: nums = [6]

Output: 6

Unfortunately, we cannot use the previous trick in this case since we cannot turn paired bits at the required position into zeros. It would be tempting to transform the given array into the format from the previous task, and then solve it in a similar way.

Reasoning this way, it's easy to notice that if we knew that we had already encountered the number N twice (or thrice) while traversing the array, we could add an additional XOR with N to the sum we are obtaining. This would make the final XOR with this number even, thereby removing it from the final sum, and what remains would be our answer.

def single_number_ii(nums: list) -> int:
    mem = {}
    result = 0

    for el in nums:
        if not mem.get(el, False):
            mem[el] = 1
        else:
            mem[el] += 1
            if mem[el] == 2:
                result ^= el
        result ^= el

    return result

Unfortunately, this solution would require a maximum of (len(nums)-1)/3 in terms of memory, which cannot be considered constant consumption, so we will have to look for another solution.

Let's try changing our approach.

Earlier, we used XOR (which represents addition modulo 2). If we had implemented addition modulo 3, we could have easily applied the trick from the previous example.

If we can put a number into the answer the first time we encounter it, put it in the accumulator the second time, and zero out both the answer and the accumulator the third time, it would help us solve the problem in one pass-through the list with additional memory consumption exactly equal to two integers, meeting the task requirements.

So, let's apply a bit more bitwise magic:

def single_number_137_ii(nums: list) -> int:
    ans, acc = 0, 0

    for n in nums:
        ans = ans ^ n & ~acc
        acc = acc ^ n & ~ans

    return ans

This way, all triple numbers get zeroed out, and we are left with only the number that occurs only once.

The Third Task Is 260. Single Number III (Medium Difficulty)

Given a non-empty array of integers where every element appears twice, except for two elements that appear only once, we need to find these unique elements. The goal is to solve the problem in O(n) time complexity and with constant extra memory, and the order of the unique elements does not matter.

Example 1:

Input: nums = [1, 2, 1, 3, 2, 5]

Output: [3, 5]

Example 2:

Input: nums = [1, -2]

Output: [-2, 1]

Obviously, we can easily eliminate all paired numbers using the XOR operation, as we did in solving the first task. The complexity of the task then lies in identifying any of the unique numbers, after which the second one can be easily computed by XOR-ing it with our XOR sum.

To achieve this, we just need to find any differing bit between these unique numbers. Then, we iterate through the array again, performing XOR summation and dividing the results into two groups - for numbers where this bit is set and for those where it is 0. As a result, we obtain the desired unique elements.

def single_number_260(nums: list) -> int:
    res1, res2 = 0, 0
    glob_xor = 0

    for n in nums:
        glob_xor ^= n

    diff_bit = glob_xor & ~(glob_xor - 1)

    for n in nums:
        if n & diff_bit:
            res1 ^= n
        else:
            res2 ^= n

    return [res1, res2]

Despite having to iterate through the array twice, the complexity remains O(n), and the memory consumption is only 2 integers.

NB: Despite the fact that int in Python is not exactly the same as int in other languages, we will consider its size as a constant