Scale Engineer

Design Bitset

Med
#1973Time: - `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.
Patterns
Design
Data structures
ArrayHash TableString

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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 10<sup>5</sup>, frequent calls to these O(size) methods would be too slow. For instance, 10<sup>5</sup> calls to flip on a bitset of size 10<sup>5</sup> would lead to an unacceptable number of operations.

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();    }}

Complexity

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.

Trade-offs

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.

Solutions

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(); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem