# Design Bitset
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-bitset)
Canonical: https://scaleengineer.com/dsa/problems/design-bitset
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table, String
---
## 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.
**Example 1:**
**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`.
# Approaches
## Naive Approach using Boolean Array
This is the most straightforward approach, where the bitset is implemented using a simple boolean array. Each index in the array corresponds to a bit, with `true` representing 1 and `false` representing 0. While simple to implement, its performance is poor for several key operations.
**Time:** - `fix(idx)`, `unfix(idx)`: O(1)
- `flip()`, `all()`, `one()`, `count()`, `toString()`: O(size) · **Space:** O(size) - to store the boolean array. Each boolean value typically occupies at least 1 byte.
**Pros:** Easy to understand and implement.
**Cons:** Very inefficient for operations that require scanning the entire bitset, such as `flip`, `count`, `all`, and `one`.; Likely to result in a 'Time Limit Exceeded' error for large inputs and frequent calls to O(size) operations.; Uses more memory than necessary (typically 1 byte per boolean) compared to packed bit representations.
### Explanation
In this approach, we use a `boolean[]` of the specified `size` as the underlying data store. The `fix` and `unfix` operations are simple O(1) assignments. However, the `flip`, `count`, `all`, and `one` operations all require a full traversal of the array, making them O(size) operations. Given the problem constraints where `size` and the number of calls can be up to 105, frequent calls to these O(size) methods would be too slow. For instance, 105 calls to `flip` on a bitset of size 105 would lead to an unacceptable number of operations.
```java
class Bitset {
boolean[] bits;
int size;
public Bitset(int size) {
this.bits = new boolean[size];
this.size = size;
}
public void fix(int idx) {
bits[idx] = true;
}
public void unfix(int idx) {
bits[idx] = false;
}
public void flip() {
for (int i = 0; i < size; i++) {
bits[i] = !bits[i];
}
}
public boolean all() {
for (int i = 0; i < size; i++) {
if (!bits[i]) {
return false;
}
}
return true;
}
public boolean one() {
for (int i = 0; i < size; i++) {
if (bits[i]) {
return true;
}
}
return false;
}
public int count() {
int count = 0;
for (int i = 0; i < size; i++) {
if (bits[i]) {
count++;
}
}
return count;
}
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < size; i++) {
sb.append(bits[i] ? '1' : '0');
}
return sb.toString();
}
}
```
### Algorithm
- **Data Structure**: A `boolean[]` array of size `size` is used to store the bits. `false` represents 0 and `true` represents 1.
- **Constructor `Bitset(size)`**: Initializes the `boolean[] bits` of the given size. By default, all values are `false` (0).
- **`fix(idx)`**: Sets `bits[idx]` to `true`.
- **`unfix(idx)`**: Sets `bits[idx]` to `false`.
- **`flip()`**: Iterates through the entire `bits` array from `0` to `size-1` and inverts each boolean value (`bits[i] = !bits[i]`).
- **`count()`**: Initializes a counter to zero. Iterates through the array, incrementing the counter for each `true` value.
- **`all()`**: Iterates through the array. If any bit is `false`, it returns `false` immediately. If the loop completes, it returns `true`.
- **`one()`**: Iterates through the array. If any bit is `true`, it returns `true` immediately. If the loop completes, it returns `false`.
- **`toString()`**: Uses a `StringBuilder` to construct the string representation by iterating through the array and appending '1' for `true` and '0' for `false`.
## Optimized Approach with Counter and Flip Flag
This approach dramatically improves the time complexity of most operations by introducing two key optimizations: a counter for set bits and a flag for the flip state. Instead of performing costly array traversals, most operations become constant time.
**Time:** - `fix(idx)`, `unfix(idx)`, `flip()`, `all()`, `one()`, `count()`: O(1)
- `toString()`: O(size) · **Space:** O(size) - to store the integer array. This is less space-efficient than a true bitset.
**Pros:** Extremely fast time complexity for all high-frequency operations (`fix`, `unfix`, `flip`, `count`, `all`, `one`).; The logic is a significant improvement and passes the time limits comfortably.
**Cons:** Uses an integer array (`int[]`) which consumes more memory (4 or 8 bytes per bit) than a boolean array or a packed bit representation.
### Explanation
The main bottleneck in the naive approach is the O(size) complexity for `flip`, `count`, `all`, and `one`. We can optimize this by avoiding the actual data manipulation until necessary.
1. **Counter for Ones**: We maintain an integer variable, `ones`, that stores the count of bits currently set to 1. This makes `count()` an O(1) operation. `all()` becomes a simple check (`ones == size`), and `one()` becomes (`ones > 0`), both O(1).
2. **Flip Flag**: Instead of iterating through the array to flip all bits, we use a boolean flag, `flipped`. Toggling this flag is an O(1) operation. When `flipped` is `true`, the meaning of the stored bits is inverted. A stored 0 is an actual 1, and a stored 1 is an actual 0. The `ones` count is updated to `size - ones` upon a flip.
The `fix` and `unfix` operations now need to account for the `flipped` flag to determine the true state of a bit before making a change. The `toString()` method is the only one that still requires an O(size) iteration, which is acceptable given its infrequent use as per the constraints.
```java
class Bitset {
int[] bits; // Stored bits
int size;
int ones; // Count of actual ones
boolean flipped;
public Bitset(int size) {
this.bits = new int[size];
this.size = size;
this.ones = 0;
this.flipped = false;
}
public void fix(int idx) {
int storedValue = bits[idx];
int actualValue = flipped ? 1 - storedValue : storedValue;
if (actualValue == 0) {
bits[idx] = 1 - storedValue; // Flip the stored bit
ones++;
}
}
public void unfix(int idx) {
int storedValue = bits[idx];
int actualValue = flipped ? 1 - storedValue : storedValue;
if (actualValue == 1) {
bits[idx] = 1 - storedValue; // Flip the stored bit
ones--;
}
}
public void flip() {
flipped = !flipped;
ones = size - ones;
}
public boolean all() {
return ones == size;
}
public boolean one() {
return ones > 0;
}
public int count() {
return ones;
}
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < size; i++) {
int storedValue = bits[i];
int actualValue = flipped ? 1 - storedValue : storedValue;
sb.append(actualValue);
}
return sb.toString();
}
}
```
### Algorithm
- **Data Structure**: An `int[]` array `bits` to store the bit values (0 or 1), an integer `ones` to track the total count of actual set bits, and a boolean `flipped` to represent the flip state.
- **Constructor `Bitset(size)`**: Initializes the `bits` array, sets `ones` to 0, and `flipped` to `false`.
- **`flip()`**: Toggles the `flipped` flag and updates the `ones` count to `size - ones`. This is an O(1) operation.
- **`count()`, `all()`, `one()`**: These operations now use the `ones` counter to return results in O(1) time.
- **`fix(idx)` / `unfix(idx)`**: These methods determine the actual current value of the bit at `idx` by considering the stored value `bits[idx]` and the `flipped` flag. If a change is needed, they flip the stored bit (`bits[idx] = 1 - bits[idx]`) and update the `ones` counter accordingly.
- **`toString()`**: This method still requires iterating through the array. For each index, it calculates the actual bit value based on the stored value and the `flipped` flag, then appends it to a `StringBuilder`.
## Space-Optimized Approach using Bit Manipulation
This approach builds upon the previous one by implementing a true, space-efficient bitset. It uses an array of integers to store the bits compactly, with each integer holding 32 (or 64 for `long`) bits. This drastically reduces memory usage while retaining the O(1) time complexity for most operations.
**Time:** - `fix(idx)`, `unfix(idx)`, `flip()`, `all()`, `one()`, `count()`: O(1)
- `toString()`: O(size) · **Space:** O(size / 32), which is O(size) with a very small constant factor. This is the most memory-efficient solution.
**Pros:** Optimal time complexity for all high-frequency operations.; Optimal space complexity, using ~8 times less memory than the boolean array approach.; Represents the standard, production-quality implementation of a bitset.
**Cons:** The implementation is more complex due to the need for bitwise arithmetic to locate and manipulate individual bits.
### Explanation
While the previous approach is optimal in terms of time, it's not optimal in space. A true bitset compactly stores bits. This approach achieves that by using an integer array where each element represents a block of 32 bits. The size of this array is `(size + 31) / 32`.
The core logic remains the same as the optimized array approach: we use a `ones` counter and a `flipped` flag to keep most operations at O(1). The main difference lies in the implementation of `fix`, `unfix`, and `toString`, which now require bitwise calculations to interact with the correct bit within the packed integer array.
This method represents the most efficient solution, providing optimal time complexity for frequent operations and optimal space complexity, making it a robust and scalable implementation.
```java
class Bitset {
int[] bits; // Stored bits, packed
int size;
int ones; // Count of actual ones
boolean flipped;
public Bitset(int size) {
this.bits = new int[(size + 31) / 32];
this.size = size;
this.ones = 0;
this.flipped = false;
}
public void fix(int idx) {
int wordIndex = idx / 32;
int bitIndex = idx % 32;
int mask = 1 << bitIndex;
int storedBit = (bits[wordIndex] & mask) == 0 ? 0 : 1;
int actualBit = flipped ? 1 - storedBit : storedBit;
if (actualBit == 0) {
// Flip the stored bit to make the actual bit 1
bits[wordIndex] ^= mask;
ones++;
}
}
public void unfix(int idx) {
int wordIndex = idx / 32;
int bitIndex = idx % 32;
int mask = 1 << bitIndex;
int storedBit = (bits[wordIndex] & mask) == 0 ? 0 : 1;
int actualBit = flipped ? 1 - storedBit : storedBit;
if (actualBit == 1) {
// Flip the stored bit to make the actual bit 0
bits[wordIndex] ^= mask;
ones--;
}
}
public void flip() {
flipped = !flipped;
ones = size - ones;
}
public boolean all() {
return ones == size;
}
public boolean one() {
return ones > 0;
}
public int count() {
return ones;
}
public String toString() {
StringBuilder sb = new StringBuilder(size);
for (int i = 0; i < size; i++) {
int wordIndex = i / 32;
int bitIndex = i % 32;
int mask = 1 << bitIndex;
int storedBit = (bits[wordIndex] & mask) == 0 ? 0 : 1;
int actualBit = flipped ? 1 - storedBit : storedBit;
sb.append(actualBit);
}
return sb.toString();
}
}
```
### Algorithm
- **Data Structure**: An `int[]` array `bits` of size `ceil(size / 32)`. Each integer in the array stores 32 bits. We also maintain `ones` (count of actual set bits) and `flipped` (flip state flag) as in the previous approach.
- **Bit Access**: To access the bit at `idx`, we find its location using `wordIndex = idx / 32` and `bitIndex = idx % 32`.
- **Bit Manipulation**: Operations like getting, setting, or flipping a specific bit are done using bitwise operators (`&`, `|`, `^`, `<<`). For example, a `mask` (`1 << bitIndex`) is used to isolate the target bit.
- **`fix(idx)` / `unfix(idx)`**: The logic is the same as the previous approach, but the implementation uses bitwise operations to read and write the stored bit within its corresponding integer word.
- **`flip()`, `count()`, `all()`, `one()`**: These are identical to the previous approach, operating in O(1) time.
- **`toString()`**: Iterates from `0` to `size-1`, and for each index `i`, it performs bitwise operations to extract the stored bit, calculates the actual bit considering the `flipped` flag, and appends it to the result string.
# Solutions
### Java
```java
class Bitset { private char [] a ; private char [] b ; private int cnt ; public Bitset ( int size ) { a = new char [ size ]; b = new char [ size ]; Arrays . fill ( a , '0' ); Arrays . fill ( b , '1' ); } public void fix ( int idx ) { if ( a [ idx ] == '0' ) { a [ idx ] = '1' ; ++ cnt ; } b [ idx ] = '0' ; } public void unfix ( int idx ) { if ( a [ idx ] == '1' ) { a [ idx ] = '0' ; -- cnt ; } b [ idx ] = '1' ; } public void flip () { char [] t = a ; a = b ; b = t ; cnt = a . length - cnt ; } public boolean all () { return cnt == a . length ; } public boolean one () { return cnt > 0 ; } public int count () { return cnt ; } public String toString () { return String . valueOf ( a ); } } /** * Your Bitset object will be instantiated and called as such: * Bitset obj = new Bitset(size); * obj.fix(idx); * obj.unfix(idx); * obj.flip(); * boolean param_4 = obj.all(); * boolean param_5 = obj.one(); * int param_6 = obj.count(); * String param_7 = obj.toString(); */
```
### CPP
```cpp
class Bitset { public: string a , b ; int cnt = 0 ; Bitset ( int size ) { a = string ( size , '0' ); b = string ( size , '1' ); } void fix ( int idx ) { if ( a [ idx ] == '0' ) a [ idx ] = '1' , ++ cnt ; b [ idx ] = '0' ; } void unfix ( int idx ) { if ( a [ idx ] == '1' ) a [ idx ] = '0' , -- cnt ; b [ idx ] = '1' ; } void flip () { swap ( a , b ); cnt = a . size () - cnt ; } bool all () { return cnt == a . size (); } bool one () { return cnt > 0 ; } int count () { return cnt ; } string toString () { return a ; } }; /** * Your Bitset object will be instantiated and called as such: * Bitset* obj = new Bitset(size); * obj->fix(idx); * obj->unfix(idx); * obj->flip(); * bool param_4 = obj->all(); * bool param_5 = obj->one(); * int param_6 = obj->count(); * string param_7 = obj->toString(); */
```
### Python
```python
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()
```