Skip to content

2166. Design Bitset

On LeetCode ->

Problem

Implement a bitset initialized with size zeros, supporting:

  • fix(idx) / unfix(idx): set a bit to 1 / 0.
  • flip(): invert every bit.
  • all() / one(): check whether every / any bit is 1.
  • count(): return the number of ones.
  • toString(): return bits in index order.
Operation     State    Return
Bitset(3)     000      -
fix(1)        010      -
flip()        101      -
unfix(0)      001      -
count()       001      1
toString()    001      "001"

class Bitset:

    def __init__(self, size: int):
        pass

    def fix(self, idx: int) -> None:
        pass

    def unfix(self, idx: int) -> None:
        pass

    def flip(self) -> None:
        pass

    def all(self) -> bool:
        pass

    def one(self) -> bool:
        pass

    def count(self) -> int:
        pass

    def toString(self) -> str:
        pass

Key trick

Store a global flip flag and a ones count: the logical bit is stored_bit ^ flipped, so flipping only toggles the flag and replaces the count with size - count.

Trap

Repeated fix or unfix must not change the count; check the logical bit, especially after a flip. Physically inverting all bits makes frequent flips too expensive.

Why is it interesting?

It demonstrates lazy updates: change how stored data is interpreted instead of modifying every element.

Python solution

class Bitset:
    def __init__(self, size: int):
        self.bits = [0] * size
        self.flipped = 0
        self.cnt = 0

    def fix(self, idx: int) -> None:
        # Only change a logical zero.
        if self.bits[idx] ^ self.flipped == 0:
            self.bits[idx] ^= 1
            self.cnt += 1

    def unfix(self, idx: int) -> None:
        # Only change a logical one.
        if self.bits[idx] ^ self.flipped == 1:
            self.bits[idx] ^= 1
            self.cnt -= 1

    def flip(self) -> None:
        # Stored bits stay unchanged; their interpretation reverses.
        self.flipped ^= 1
        self.cnt = len(self.bits) - self.cnt

    def all(self) -> bool:
        return self.cnt == len(self.bits)

    def one(self) -> bool:
        return self.cnt > 0

    def count(self) -> int:
        return self.cnt

    def toString(self) -> str:
        return "".join(str(x ^ self.flipped) for x in self.bits)

Time: Initialization and toString() take \(O(n)\); every other operation takes \(O(1)\).

Space: \(O(n)\) storage; toString() additionally uses \(O(n)\) space.

Comment on my solution

Your solution is functionally correct; the timeout comes from flip(), which constructs a full set and costs \(O(n)\) per call, giving \(O(qn)\) time for \(q\) flips.

The sparse-set idea is valid, but flipping can make the set dense. A flip flag would let the set represent stored ones rather than logical ones, preserving average \(O(1)\) updates and flips.

# Ideas:
# - It reminds me of problem about sparse vector where almost all
#   element are zeros so we could keep only map (index->val) for value
#   that are not 0

# WRONG
# Time Limit Exceeded: 44/48 testcases passed
class Bitset:
    def __init__(self, size: int):
        self.size = size
        self.ones = set() # set of index with set bit

    def fix(self, idx: int) -> None:
        self.ones.add(idx)

    def unfix(self, idx: int) -> None:
        self.ones.discard(idx)

    def flip(self) -> None:
        self.ones = set(range(self.size)) - self.ones

    def all(self) -> bool:
        return len(self.ones) == self.size

    def one(self) -> bool:
        return len(self.ones) > 0

    def count(self) -> int:
        return len(self.ones)

    def toString(self) -> str:
        bits = [0] * self.size
        for i in self.ones:
            bits[i] = 1
        return "".join(map(str, bits))