unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 137: Single Number II

link

We can create a map: {number -> count}. In the map, the number that has count = 1 is the one we want.

Assuming numbers are 32-bit integers, there are 2^{32} distinct numbers.

Time: \mathcal{O}(n), space: \mathcal{O}(n).

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num_count = {}
        for x in nums:
            num_count[x] = num_count.get(x, 0) + 1

        return next(x for x in num_count if num_count[x] == 1)

Above, the count of numbers have a pattern: it is either multiple of 3 or 1. We can follow similar approach but at the bit level. We can count 0’s and 1’s at each bit position (for all numbers) and these two counts, the number of zeros and the number of ones, should show the same pattern. In that way, we can deduce our number one bit at a time. Since each number has at most 32 bits, we would have 32 \cdot n iterations in total. So, time is still \mathcal{O}(n).

In Python, the int’s are infinite precision. So, while counting zeros and ones, we consider each number as 32-bit unsigned integer and in the end convert it to negative if the magnitude \ge 2^{31}.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def get_bit_at(self, i, nums):
        one_count, zero_count = 0, 0
        for x in nums:
            # Consider x as 32-bit unsigned
            x &= 0xFFFFFFFF
            x = x >> i
            if x & 1:
                one_count += 1
            else:
                zero_count += 1
        
        if one_count == 0:
            return 0
        if zero_count == 0:
            return 1
        if one_count % 3 == 0:
            return 0
        if zero_count % 3 == 0:
            return 1

    def set_bit_at(self, x, pos, val):
        if val == 0:
            return x & ~(1 << pos)
        else:
            return x | (1 << pos)

    def singleNumber(self, nums: List[int]) -> int:
        x = 0
        for i in range(32):
            val = self.get_bit_at(i, nums)
            x = self.set_bit_at(x, i, val)

        if x < (1 << 31):
            return x
        
        # x is negative
        # -1 has same bit representation as (2^32 - 1)
        return x - (1 << 32)

Note, with 32 bits, the two’s complement bit representation of -1 and 2^{32}-1 are same, representation of -2 and 2^{32}-2 are same, etc. So, to convert the magnitude to negative we subtract 2^{32}.

from collections import deque

def get_bit_representation(x, bit_count):
    bits = deque()
    for i in range(bit_count):
        bits.appendleft(1 if x & (1 << i) else 0)
    return "".join(str(b) for b in bits)

tanvirdotzaman

,

Leave a comment