#2166

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Design Bitset

Master the Design Bitset problem by efficiently managing bit flips, counts, and indexed updates with array and hash lookup techniques.

array hash table string design

Problem Statement

Implement a Bitset class that stores a sequence of bits initialized to 0. The class must support operations to fix a bit to 1, unfix a bit to 0, flip all bits, check if all bits are 1, check if at least one bit is 1, count the number of bits set to 1, and return the current bitset as a string. Each operation must run efficiently, even with up to 100,000 calls.

The Bitset should handle indexing from 0 to size - 1, and flipping a bit twice should not change its final state. You must optimize for both time and space using array scanning plus hash lookup, ensuring that operations like all, one, count, and toString return accurate results under heavy operation sequences.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"] [[5], [3], [1], [], [], [0], [], [], [0], [], []] Output [null, null, null, null, false, null, null, true, null, 2, "01010"]

Explanation Bitset bs = new Bitset(5); // bitset = "00000". bs.fix(3); // the value at idx = 3 is updated to 1, so bitset = "00010". bs.fix(1); // the value at idx = 1 is updated to 1, so bitset = "01010". bs.flip(); // the value of each bit is flipped, so bitset = "10101". bs.all(); // return False, as not all values of the bitset are 1. bs.unfix(0); // the value at idx = 0 is updated to 0, so bitset = "00101". bs.flip(); // the value of each bit is flipped, so bitset = "11010". bs.one(); // return True, as there is at least 1 index with value 1. bs.unfix(0); // the value at idx = 0 is updated to 0, so bitset = "01010". bs.count(); // return 2, as there are 2 bits with value 1. bs.toString(); // return "01010", which is the composition of bitset.

Constraints

1 <= size <= 105
0 <= idx <= size - 1
At most 105 calls will be made in total to fix, unfix, flip, all, one, count, and toString.
At least one call will be made to all, one, count, or toString.
At most 5 calls will be made to toString.

Solution Approach

Use array and auxiliary counters

Maintain an array representing the bitset and use counters for the number of bits set to 1. Each fix or unfix updates the array and the counter, while flip inverts the array logically or via a flipped flag. This reduces repeated scanning for operations like all or count.

Track flipped indices with a hash

Store the indices of flipped bits in a hash or set to quickly determine their effective value after multiple flips. This ensures fix, unfix, and flip operations consider the current logical state without scanning the entire array each time.

Optimize toString and count

For toString, generate the output based on the flipped flag and hash set to avoid iterating the whole array unnecessarily. Count can be maintained incrementally by updating the counter on each fix, unfix, or flip, enabling O(1) queries for one and all operations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on implementation choices: using an array with a flipped flag and hash for indices gives O(1) for fix, unfix, one, all, and count, while toString takes O(n). Space is O(n) for the array and O(k) for the flipped indices hash.

What Interviewers Usually Probe

Expecting an O(1) approach for fix, unfix, one, all, and count operations.
Looking for use of an auxiliary data structure to track flipped bits efficiently.
Checking if the candidate handles multiple flips correctly without full rescans.

Common Pitfalls or Variants

Common pitfalls

Scanning the entire array for every operation, leading to TLE for large n.
Incorrectly updating counters after flip operations, causing wrong all or count results.
Failing to account for multiple flips, leading to inconsistent bit values.

Follow-up variants

Implement a dynamic-size Bitset that can expand beyond the initial size while maintaining operation efficiency.
Support batch flip operations for a range of indices instead of flipping all bits at once.
Extend Bitset to track not only counts but also the positions of set bits efficiently.

FAQ

What is the best way to handle multiple flips in Design Bitset?

Use a flipped flag and track flipped indices with a hash so that each flip operation updates logical state without rescanning the entire array.

How do you implement the count operation efficiently?

Maintain a counter that updates incrementally with fix, unfix, and flip, avoiding repeated scans of the bitset.

Can toString be optimized in this problem?

Yes, use the flipped flag and hash of flipped indices to generate the string without iterating the full array each time.

Why use a hash in addition to the array?

The hash allows O(1) access to track flipped indices, ensuring fix and unfix respect the current logical state after flips.

What pattern is central to solving Design Bitset?

The core pattern is array scanning plus hash lookup, optimizing bit updates and queries under multiple flips.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

class Bitset:
    def __init__(self, size: int):
        self.a = ['0'] * size
        self.b = ['1'] * size
        self.cnt = 0

    def fix(self, idx: int) -> None:
        if self.a[idx] == '0':
            self.a[idx] = '1'
            self.cnt += 1
        self.b[idx] = '0'

    def unfix(self, idx: int) -> None:
        if self.a[idx] == '1':
            self.a[idx] = '0'
            self.cnt -= 1
        self.b[idx] = '1'

    def flip(self) -> None:
        self.a, self.b = self.b, self.a
        self.cnt = len(self.a) - self.cnt

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

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

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

    def toString(self) -> str:
        return ''.join(self.a)


# Your Bitset object will be instantiated and called as such:
# obj = Bitset(size)
# obj.fix(idx)
# obj.unfix(idx)
# obj.flip()
# param_4 = obj.all()
# param_5 = obj.one()
# param_6 = obj.count()
# param_7 = obj.toString()

Continue Practicing

#2227 encrypt and decrypt strings #2353 design a food rating system #2135 count words obtained after adding a letter