LeetCode Solutions Blog

Design Bitset

Number: 2285

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Design a Bitset class that efficiently stores a sequence of bits and supports operations to fix (set to 1), unfix (set to 0), flip (invert all bits), and query the status of bits (check if all are 1, if at least one is 1, count the number of 1s, and represent the Bitset as a string).

Key Insights

Instead of updating every bit during a flip operation, maintain a boolean flag (isFlipped) to indicate if the bits are logically inverted.
Use an array (or equivalent) to store the bits in their original state.
Adjust fix and unfix methods to account for the current flipped state when updating a particular bit.
Maintain a counter (countOne) to track the number of bits set to 1 efficiently.
When flip is called, update the counter as (size - countOne) without iterating through all bits.

Space and Time Complexity

Time Complexity:

fix, unfix, flip, all, one, count: O(1)
toString: O(n) (with at most 5 calls overall)

Space Complexity:

O(n) for storing the bit array

Solution

The solution uses an array to keep track of the bits and a boolean flag to indicate a global "flip" state. The actual effective value of a bit is computed by XOR-ing the stored bit with the flip flag (interpreted as 0 or 1). This allows the flip operation to be O(1) by simply toggling the flag and updating a maintained counter (countOne). Both fix and unfix adjust the stored bit according to whether the Bitset is currently flipped or not. This design ensures that all operations are efficient and work within the given constraints.

Code Solutions

# Python implementation of the Bitset class

class Bitset:
    def __init__(self, size: int):
        # Initialize Bitset with given size, all bits are 0
        self.n = size                # Total number of bits
        self.bits = [0] * size       # List storing the bits (original state)
        self.countOne = 0            # Number of bits set to 1 (effective)
        self.isFlipped = False       # Global flag representing flipped state

    def fix(self, idx: int) -> None:
        # Get the effective current value using XOR with the flip state
        current = self.bits[idx] ^ self.isFlipped
        # If already 1, do nothing
        if current == 1:
            return
        # Set the bit to effective value 1:
        # if Bitset is flipped, setting effective 1 means storing 0, otherwise 1.
        self.bits[idx] = 0 if self.isFlipped else 1
        self.countOne += 1

    def unfix(self, idx: int) -> None:
        current = self.bits[idx] ^ self.isFlipped
        # If already 0, do nothing
        if current == 0:
            return
        # Set the bit to effective value 0:
        # if Bitset is flipped, setting effective 0 means storing 1, otherwise 0.
        self.bits[idx] = 1 if self.isFlipped else 0
        self.countOne -= 1

    def flip(self) -> None:
        # Toggle the flip flag and update the 1's counter accordingly.
        self.isFlipped = not self.isFlipped
        self.countOne = self.n - self.countOne

    def all(self) -> bool:
        # Check if all bits are effectively 1.
        return self.countOne == self.n

    def one(self) -> bool:
        # Check if at least one bit is effectively 1.
        return self.countOne > 0

    def count(self) -> int:
        # Return the effective count of bits that are 1.
        return self.countOne

    def toString(self) -> str:
        # Build the string representing the current effective Bitset.
        result = []
        for bit in self.bits:
            effective = bit ^ self.isFlipped
            result.append(str(effective))
        return "".join(result)