unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1009: Complement of Base 10 Integer

link

To find the complement we can xor with all-ones mask. To create the all-ones mask, we first find the leftmost 1-bit in n. Say i-th bit is the leftmost 1-bit. Then, (2^{i+1} - 1) will have all bits right of i set to 1’s and that is our mask.

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

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        mask = 1 << 31
        for i in range(31, -1, -1):
            if n & mask:
                return ((1 << (i+1)) - 1) ^ n
            else:
                mask >>= 1
        # No 1-bit, so n = 0
        return 1

We can create the all-ones mask without explicitly finding the leftmost 1 in n.

Above, first or creates two 1’s. Next or doubles the number of 1-bits in the mask. We keep doubling the 1-bits in the mask.

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        max_bit_count = 32
        mask = n
        one_fill = 1
        while one_fill < max_bit_count:
            mask |= (mask >> one_fill)
            one_fill <<= 1
        
        return n ^ max(1, mask)

tanvirdotzaman

,

Leave a comment