LeetCode Solutions Blog

Design Bitset

Difficulty: Medium

Problem Description

A Bitset is a data structure that compactly stores bits. The task is to implement a Bitset class with various operations to manipulate the bits.

Key Insights

A Bitset consists of bits that can be either 0 or 1.
Operations include setting a bit to 1, resetting a bit to 0, flipping all bits, and checking the status of the bits.
Efficient implementation is necessary to handle up to 100,000 operations.

Space and Time Complexity

Time Complexity:

O(1) for fix, unfix, and count.
O(n) for flip and toString.
O(1) for one and all.

Space Complexity: O(n) for storing the bits.

Solution

To solve the problem, we will use an array to represent the bits of the Bitset. Each index of the array corresponds to a bit, where 0 represents 'off' and 1 represents 'on'. We will also maintain a counter to quickly track the number of bits that are set to 1. The flip operation will toggle the bits, and we will use a boolean flag to keep track of whether the bits are currently in their original or flipped state.

Code Solutions

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

    def fix(self, idx: int) -> None:
        if self.flipped:
            if self.bits[idx] == 0:
                self.bits[idx] = 1
                self.count_ones -= 1
        else:
            if self.bits[idx] == 1:
                return
            self.bits[idx] = 1
            self.count_ones += 1

    def unfix(self, idx: int) -> None:
        if self.flipped:
            if self.bits[idx] == 1:
                self.bits[idx] = 0
                self.count_ones += 1
        else:
            if self.bits[idx] == 0:
                return
            self.bits[idx] = 0
            self.count_ones -= 1

    def flip(self) -> None:
        self.flipped = not self.flipped
        self.count_ones = self.size - self.count_ones

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

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

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

    def toString(self) -> str:
        return ''.join(str(1 - bit) if self.flipped else str(bit) for bit in self.bits)