2166. Design Bitset

MediumDesignArrayHash Table

Problem Description

The task is to create a Bitset class that behaves like a binary set of fixed size, capable of individual bit manipulations. Here's a breakdown of the class functionality:

Bitset(int size): Construct a Bitset with the specified number of bits, all initially set to 0.
void fix(int idx): Set the bit at the specified index to 1.
void unfix(int idx): Set the bit at the specified index to 0.
void flip(): Invert all the bits in the Bitset (0s become 1s and vice versa).
boolean all(): Check if all bits are set to 1.
boolean one(): Check if there is at least one bit set to 1.
int count(): Return the number of bits set to 1.
String toString(): Represent the Bitset as a string of '0's and '1's.

The Bitset class is to be implemented in a way that these operations are performed efficiently, and the current state of the Bitset can be retrieved or checked as required.

Intuition

The intuitive approach to solving this problem is to maintain the Bitset using an array or a string where each index represents a bit. However, an additional layer of complexity is introduced by the flip() method, which in a naive implementation could be costly (in terms of time) if we had to flip each bit individually.

To optimize, we can use two arrays: one that represents the Bitset (self.a) and another that represents the flipped state of the Bitset (self.b). Whenever a flip operation is called, instead of flipping each bit, we can simply swap references between these two arrays.

Along with this, we maintain a counter (self.cnt) to keep track of the number of bits set to 1, which allows constant-time access to the count, and efficient implementation of all(), one(), and count() methods:

For fix(idx), set the bit at idx to 1 in self.a and to 0 in self.b, and adjust the counter if the bit was previously 0.
Similarly for unfix(idx), set the bit at idx to 0 in self.a and to 1 in self.b, adjusting the counter if the bit was previously 1.
The flip() method simply swaps the references between self.a and self.b and updates the counter to reflect the flipped state.
all() checks if the counter is equal to the size of the Bitset.
one() checks if the counter is greater than 0.
count() returns the value of the counter.
toString() returns self.a as a string, representing the current state of the Bitset.

This solution ensures that all the operations are performed in O(1) or O(n) time complexity, where n is the size of the Bitset, making the operations efficient and the class practical for use.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The solution utilizes a dual list representation as the core data structure and keeps a count of how many bits are set to 1 for efficient counter updates. Here is how the implementation aligns with algorithmic concepts:

Array Operations: The class uses two arrays, self.a and self.b, corresponding to the bitset and its inverse. Array indices correspond to bit positions, and array values ('0' or '1') represent the bit's value.
Bit Manipulation: Although we're not using bitwise operators directly, the operations fix, unfix, and flip mimic bitwise operations at a higher abstraction level, where individual elements in arrays are set to '0' or '1', or swapped.
Reference Swapping: The initial instinct might be to iterate through all bits and flip them individually, but this would be inefficient. Instead, flipping is done by swapping pointers (references) to the two arrays, a constant-time operation, thus giving the illusion of flipping all bits instantly.
Counter Cache: A counter (self.cnt) is maintained and updated during fix and unfix operations, which provides instant access to the number of set bits. This avoids the need to iterate through the entire bitset to count the bits for the count, all, and one operations.

Walking through each method in detail:

__init__(self, size: int): Initializes the bitset (self.a) and its inverse (self.b) as lists filled with '0's and '1's, respectively, and sets the count (self.cnt) to 0.
fix(self, idx: int): Sets the bit at idx to '1' in self.a if it is not already '1', increasing self.cnt accordingly. self.b at idx is set to '0', as it always holds the inverse values.
unfix(self, idx: int): Sets the bit at idx to '0' in self.a if it is not already '0', decreasing self.cnt accordingly. self.b at idx is set to '1'.
flip(self): Swaps self.a with self.b and updates self.cnt to reflect the number of bits set to '1', which can be computed as the size of the bitset minus the old count.
all(self): Determines if all bits are '1's in self.a by checking if self.cnt is equal to the size of the bitset.
one(self): Determines if at least one bit is '1' by checking if self.cnt is greater than 0.
count(self): Simply returns self.cnt, which is already the number of bits set to '1'.
toString(self): Returns the current composition of the bitset by joining all elements of self.a into a string.

This approach takes advantage of the primary operations with arrays in Python and uses a strategy to keep time complexity manageable for operations that could potentially be costly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

[1, 2, 3, 4, 5][1, 3, 6, 10, 15][15, 14, 12, 9, 5][5, 4, 3, 2, 1]

I don’t know

Example Walkthrough

Let's go through a small example to illustrate the solution approach using the Bitset class with a bitset of size 5.

Bitset bitset = new Bitset(5) initializes the bitset. Now bitset.a is ['0', '0', '0', '0', '0'], bitset.b is ['1', '1', '1', '1', '1'], and bitset.cnt is 0.
bitset.fix(2) sets the third bit (0-indexed) to '1'. Now bitset.a is ['0', '0', '1', '0', '0'], bitset.b is ['1', '1', '0', '1', '1'], and bitset.cnt is 1.
bitset.fix(4) sets the fifth bit to '1'. Now bitset.a is ['0', '0', '1', '0', '1'], bitset.b is ['1', '1', '0', '1', '0'], and bitset.cnt is 2.
bitset.unfix(2) sets the third bit back to '0'. Now bitset.a is ['0', '0', '0', '0', '1'], bitset.b is ['1', '1', '1', '1', '0'], and bitset.cnt is 1.
bitset.flip() swaps the bitset with its inverse. Now bitset.a is ['1', '1', '1', '1', '0'], bitset.b is ['0', '0', '0', '0', '1'], and bitset.cnt is updated to 4, which is 5 (size of bitset) minus 1 (old count).
bitset.all() checks if all bits are '1'. In our case, bitset.cnt is 4 which is not equal to the bitset size 5, so it returns false.
bitset.one() checks if there's at least one bit that is '1'. Since bitset.cnt is 4 which is greater than 0, it returns true.
bitset.count() simply returns bitset.cnt, which is 4 at this point.
bitset.toString() would return the string representation of bitset.a which is now '11110'.

This example demonstrates that by using two arrays and keeping track of the count of '1's, we can perform operations like fix, unfix, flip, all, one, count, and toString efficiently and maintain an accurate representation of the bitset through all the changes.

Solution Implementation

1class Bitset:
2    def __init__(self, size: int):
3        # Initialize two bit representations. One is the regular,
4        # the other is the inverse. Also initialize the count of '1's in the regular representation.
5        self.regular_bits = ['0'] * size
6        self.inverse_bits = ['1'] * size
7        self.ones_count = 0
8
9    def fix(self, idx: int) -> None:
10        # Set the bit at the given index to '1' in the regular bitmap,
11        # and to '0' in the inverse bitmap only if it is not already set.
12        if self.regular_bits[idx] == '0':
13            self.regular_bits[idx] = '1'
14            self.inverse_bits[idx] = '0'
15            self.ones_count += 1  # Increase the count of '1's
16
17    def unfix(self, idx: int) -> None:
18        # Set the bit at the given index to '0' in the regular bitmap,
19        # and to '1' in the inverse bitmap only if it is currently set.
20        if self.regular_bits[idx] == '1':
21            self.regular_bits[idx] = '0'
22            self.inverse_bits[idx] = '1'
23            self.ones_count -= 1  # Decrease the count of '1's
24
25    def flip(self) -> None:
26        # Swap the regular bitmap with the inverse, and update the count of '1's accordingly.
27        self.regular_bits, self.inverse_bits = self.inverse_bits, self.regular_bits
28        self.ones_count = len(self.regular_bits) - self.ones_count
29
30    def all(self) -> bool:
31        # Return True if all bits are '1', which means the count of '1's equals the size of the bit array.
32        return self.ones_count == len(self.regular_bits)
33
34    def one(self) -> bool:
35        # Return True if at least one bit is '1', indicated by a count greater than zero.
36        return self.ones_count > 0
37
38    def count(self) -> int:
39        # Return the number of '1's in the bitset.
40        return self.ones_count
41
42    def toString(self) -> str:
43        # Create a string representation of the bits array.
44        return ''.join(self.regular_bits)
45
46
47# Your Bitset object will be instantiated and called as such:
48# obj = Bitset(size)
49# obj.fix(idx)
50# obj.unfix(idx)
51# obj.flip()
52# param_4 = obj.all()
53# param_5 = obj.one()
54# param_6 = obj.count()
55# param_7 = obj.toString()
56

1import java.util.Arrays;
2
3class Bitset {
4    private char[] bits;    // Array representing the bitset.
5    private char[] invertedBits; // Array representing the inverted bitset.
6    private int countOnes;  // Count of ones in the bitset.
7
8    // Initializes the Bitset with a fixed size.
9    public Bitset(int size) {
10        bits = new char[size];
11        invertedBits = new char[size];
12        Arrays.fill(bits, '0'); // Set all bits to 0 initially.
13        Arrays.fill(invertedBits, '1'); // Set all inverted bits to 1 initially.
14    }
15
16    // Sets the bit at index `idx` to 1.
17    public void fix(int idx) {
18        if (bits[idx] == '0') { // Check if the bit is currently 0.
19            bits[idx] = '1'; // Set the bit to 1.
20            countOnes++; // Increment the count of ones.
21        }
22        invertedBits[idx] = '0'; // Set the corresponding bit in the inverted array to 0.
23    }
24
25    // Resets the bit at index `idx` to 0.
26    public void unfix(int idx) {
27        if (bits[idx] == '1') { // Check if the bit is currently 1.
28            bits[idx] = '0'; // Set the bit to 0.
29            countOnes--; // Decrement the count of ones.
30        }
31        invertedBits[idx] = '1'; // Set the corresponding bit in the inverted array to 1.
32    }
33
34    // Inverts the bitset (1's to 0's and 0's to 1's).
35    public void flip() {
36        // Swap the reference of bits and invertedBits.
37        char[] temp = bits;
38        bits = invertedBits;
39        invertedBits = temp;
40
41        // Update the count of ones in the bitset.
42        countOnes = bits.length - countOnes; 
43    }
44
45    // Checks if all bits are set to 1.
46    public boolean all() {
47        return countOnes == bits.length; // True if count of ones equals the length of the bitset.
48    }
49
50    // Checks if at least one bit is set to 1.
51    public boolean one() {
52        return countOnes > 0; // True if there is at least one bit set to 1.
53    }
54
55    // Counts the number of bits set to 1 in the bitset.
56    public int count() {
57        return countOnes; // Returns the count of ones.
58    }
59
60    // Returns a string representation of the bitset.
61    public String toString() {
62        return new String(bits); // Convert the bits array to a string. 
63    }
64}
65
66// Example on how to instantiate and use the Bitset:
67// Bitset bitset = new Bitset(size);
68// bitset.fix(idx);
69// bitset.unfix(idx);
70// bitset.flip();
71// boolean isAllSet = bitset.all();
72// boolean isOneSet = bitset.one();
73// int oneCount = bitset.count();
74// String bitsetString = bitset.toString();
75

1class Bitset {
2private:
3    std::string bitset;    // the primary string representing the bitset
4    std::string inverse;   // the inverse of the primary string
5    int countOnes = 0;     // counter to keep track of the number of set bits
6
7public:
8    // Constructor initializes the bitset and its inverse with the specified size.
9    Bitset(int size): bitset(size, '0'), inverse(size, '1') {}
10
11    // Sets the bit at the given index to 1 if it is not already.
12    void fix(int idx) {
13        if (bitset[idx] == '0') {
14            bitset[idx] = '1';
15            ++countOnes;
16            inverse[idx] = '0';
17        }
18    }
19
20    // Sets the bit at the given index to 0 if it is not already.
21    void unfix(int idx) {
22        if (bitset[idx] == '1') {
23            bitset[idx] = '0';
24            --countOnes;
25            inverse[idx] = '1';
26        }
27    }
28
29    // Flips all bits in the bitset.
30    void flip() {
31        // Swap bitset and inverse to flip all bits
32        std::swap(bitset, inverse);
33        // Update the set bits count to reflect the flipping
34        countOnes = bitset.size() - countOnes;
35    }
36
37    // Checks if all bits are set to 1.
38    bool all() {
39        return countOnes == bitset.size();
40    }
41
42    // Checks if at least one bit is set to 1.
43    bool one() {
44        return countOnes > 0;
45    }
46
47    // Returns the number of bits that are set to 1.
48    int count() {
49        return countOnes;
50    }
51
52    // Returns the string representation of the bitset.
53    std::string toString() {
54        return bitset;
55    }
56};
57
58/**
59 * Usage example:
60 * Bitset* bitsetObj = new Bitset(size);
61 * bitsetObj->fix(idx);
62 * bitsetObj->unfix(idx);
63 * bitsetObj->flip();
64 * bool isAllSet = bitsetObj->all();
65 * bool isOneSet = bitsetObj->one();
66 * int numOfOnes = bitsetObj->count();
67 * std::string bitsetStr = bitsetObj->toString();
68 * delete bitsetObj; // Don't forget to free the memory when done
69 */
70

1// Initialize global variables to replicate class properties
2let bitset: string;
3let inverse: string;
4let countOnes: number = 0;
5
6// Initialize function to set up the bitset and its inverse (replaces constructor)
7function initialize(size: number): void {
8    bitset = '0'.repeat(size);
9    inverse = '1'.repeat(size);
10}
11
12// Function to set the bit at the given index to 1 if it is not already (replaces 'fix' method)
13function fix(idx: number): void {
14    if (bitset[idx] === '0') {
15        bitset = bitset.substring(0, idx) + '1' + bitset.substring(idx + 1);
16        countOnes++;
17        inverse = inverse.substring(0, idx) + '0' + inverse.substring(idx + 1);
18    }
19}
20
21// Function to set the bit at the given index to 0 if it is not already (replaces 'unfix' method)
22function unfix(idx: number): void {
23    if (bitset[idx] === '1') {
24        bitset = bitset.substring(0, idx) + '0' + bitset.substring(idx + 1);
25        countOnes--;
26        inverse = inverse.substring(0, idx) + '1' + inverse.substring(idx + 1);
27    }
28}
29
30// Function to flip all bits in the bitset (replaces 'flip' method)
31function flip(): void {
32    [bitset, inverse] = [inverse, bitset];
33    countOnes = bitset.length - countOnes;
34}
35
36// Function to check if all bits are set to 1 (replaces 'all' method)
37function all(): boolean {
38    return countOnes === bitset.length;
39}
40
41// Function to check if at least one bit is set to 1 (replaces 'one' method)
42function one(): boolean {
43    return countOnes > 0;
44}
45
46// Function to return the number of bits that are set to 1 (replaces 'count' method)
47function count(): number {
48    return countOnes;
49}
50
51// Function to return the string representation of the bitset (replaces 'toString' method)
52function toString(): string {
53    return bitset;
54}
55
56// Usage example:
57// initialize(size);
58// fix(idx);
59// unfix(idx);
60// flip();
61// const isAllSet = all();
62// const isOneSet = one();
63// const numOfOnes = count();
64// const bitsetStr = toString();
65

Not Sure What to Study? Take the 2-min Quiz：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's fasterIt has better space complexityOrder of computer subproblems does not matterIt has better time complexity

I don’t know

Time and Space Complexity

Time Complexity

__init__(self, size: int): The initialization runs in O(size) time because it initializes two lists with size elements each.
fix(self, idx: int) -> None: This method operates in O(1) time since it involves a couple of constant-time operations – checking if an element is '0' and setting a list element by index.
unfix(self, idx: int) -> None: Similar to fix, this method also operates in O(1) time due to direct element access and assignment.
flip(self) -> None: The flip operation is O(1) because it swaps references between self.a and self.b and calculates the new count of '1's without iterating over the whole list.
all(self) -> bool: Checking if all bits are '1' is O(1) as it compares a single integer self.cnt to the size of the list len(self.a).
one(self) -> bool: Just like all, checking for at least one '1' bit is O(1) since it only requires a single conditional check of self.cnt.
count(self) -> int: Returning the count is O(1) because it simply returns the value of self.cnt.
toString(self) -> str: Converting the bitset to string representation is O(size) because it joins a list of size elements into a single string.

Space Complexity

The overall space complexity of the Bitset class is O(size). The two lists self.a and self.b each require O(size) space, and the integer self.cnt requires O(1) space. Hence, the total space required remains O(size), taking into account both lists.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

O(1)O(n)O(n!)O(n^n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2166. Design Bitset

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings