Problem

A Bitset is a data structure that compactly stores bits.

Implement the Bitset class:

  • Bitset(int size) Initializes the Bitset with size bits, all of which are 0.
  • void fix(int idx) Updates the value of the bit at the index idx to 1. If the value was already 1, no change occurs.
  • void unfix(int idx) Updates the value of the bit at the index idx to 0. If the value was already 0, no change occurs.
  • void flip() Flips the values of each bit in the Bitset. In other words, all bits with value 0 will now have value 1 and vice versa.
  • boolean all() Checks if the value of each bit in the Bitset is 1. Returns true if it satisfies the condition, false otherwise.
  • boolean one() Checks if there is at least one bit in the Bitset with value 1. Returns true if it satisfies the condition, false otherwise.
  • int count() Returns the total number of bits in the Bitset which have value 1.
  • String toString() Returns the current composition of the Bitset. Note that in the resultant string, the character at the ith index should coincide with the value at the ith bit of the Bitset.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


    
    
    **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 <= 10^5
  • 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

Method 1 – Lazy Flip with Count Tracking

Intuition

To efficiently support fix, unfix, flip, and query operations, we use a lazy flip approach. Instead of flipping all bits, we maintain a flip flag and invert the meaning of 0 and 1 when the flag is set. We also track the count of 1s for fast queries.

Approach

  1. Use an array bits to store the current state of each bit (0 or 1).
  2. Maintain a flip_flag to indicate if the bits are flipped.
  3. Track the count of 1s (ones_count).
  4. For fix(idx), set the bit at idx to 1 (considering flip), update ones_count if changed.
  5. For unfix(idx), set the bit at idx to 0 (considering flip), update ones_count if changed.
  6. For flip(), toggle the flip_flag and update ones_count to size - ones_count.
  7. For all(), check if ones_count == size.
  8. For one(), check if ones_count > 0.
  9. For count(), return ones_count.
  10. For toString(), build the string considering the flip flag.

Code

 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

class Bitset:
    def __init__(self, size: int):
        self.n = size
        self.bits = [0] * size
        self.flip_flag = False
        self.ones_count = 0
    def fix(self, idx: int) -> None:
        v = self.bits[idx] ^ self.flip_flag
        if v == 0:
            self.bits[idx] ^= 1
            self.ones_count += 1
    def unfix(self, idx: int) -> None:
        v = self.bits[idx] ^ self.flip_flag
        if v == 1:
            self.bits[idx] ^= 1
            self.ones_count -= 1
    def flip(self) -> None:
        self.flip_flag ^= 1
        self.ones_count = self.n - self.ones_count
    def all(self) -> bool:
        return self.ones_count == self.n
    def one(self) -> bool:
        return self.ones_count > 0
    def count(self) -> int:
        return self.ones_count
    def toString(self) -> str:
        return ''.join(str(b ^ self.flip_flag) for b in self.bits)
 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
45

public class Bitset {
    private int n, onesCount;
    private boolean flipFlag;
    private int[] bits;
    public Bitset(int size) {
        n = size;
        bits = new int[n];
        flipFlag = false;
        onesCount = 0;
    }
    public void fix(int idx) {
        int v = bits[idx] ^ (flipFlag ? 1 : 0);
        if (v == 0) {
            bits[idx] ^= 1;
            onesCount++;
        }
    }
    public void unfix(int idx) {
        int v = bits[idx] ^ (flipFlag ? 1 : 0);
        if (v == 1) {
            bits[idx] ^= 1;
            onesCount--;
        }
    }
    public void flip() {
        flipFlag = !flipFlag;
        onesCount = n - onesCount;
    }
    public boolean all() {
        return onesCount == n;
    }
    public boolean one() {
        return onesCount > 0;
    }
    public int count() {
        return onesCount;
    }
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(bits[i] ^ (flipFlag ? 1 : 0));
        }
        return sb.toString();
    }
}