2166. Design Bitset LeetCode Solution

Last updated: February 26, 2025

In this guide, you will get 2166. Design Bitset LeetCode Solution with the best time and space complexity. The solution to Design Bitset problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Design Bitset solution in C++
Design Bitset solution in Java
Design Bitset solution in Python
Additional Resources

2166. Design Bitset LeetCode Solution image

Problem Statement of Design Bitset

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.

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(|\texttt{size}|)

2166. Design Bitset LeetCode Solution in C++

class Bitset {
 public:
  Bitset(int size) : s(size, '0'), r(size, '1') {}

  void fix(int idx) {
    if (s[idx] == '0')
      ++cnt;
    s[idx] = '1';
    r[idx] = '0';
  }

  void unfix(int idx) {
    if (s[idx] == '1')
      --cnt;
    s[idx] = '0';
    r[idx] = '1';
  }

  void flip() {
    swap(s, r);
    cnt = s.length() - cnt;
  }

  bool all() {
    return cnt == s.length();
  }

  bool one() {
    return cnt;
  }

  int count() {
    return cnt;
  }

  string toString() {
    return s;
  }

 private:
  string s;  // the original
  string r;  // the reversed
  int cnt = 0;
};
/* code provided by PROGIEZ */

2166. Design Bitset LeetCode Solution in Java

class Bitset {
  public Bitset(int size) {
    for (int i = 0; i < size; ++i) {
      sb.append('0');
      rb.append('1');
    }
  }

  public void fix(int idx) {
    if (sb.charAt(idx) == '0')
      ++cnt;
    sb.setCharAt(idx, '1');
    rb.setCharAt(idx, '0');
  }

  public void unfix(int idx) {
    if (sb.charAt(idx) == '1')
      --cnt;
    sb.setCharAt(idx, '0');
    rb.setCharAt(idx, '1');
  }

  public void flip() {
    StringBuilder temp = sb;
    sb = rb;
    rb = temp;
    cnt = sb.length() - cnt;
  }

  public boolean all() {
    return cnt == sb.length();
  }

  public boolean one() {
    return cnt > 0;
  }

  public int count() {
    return cnt;
  }

  public String toString() {
    return sb.toString();
  }

  private StringBuilder sb = new StringBuilder(); // the original
  private StringBuilder rb = new StringBuilder(); // the reversed
  private int cnt = 0;
}
// code provided by PROGIEZ

2166. Design Bitset LeetCode Solution in Python

class Bitset:
  def __init__(self, size: int):
    self.s = ['0'] * size  # the original
    self.r = ['1'] * size  # the reversed
    self.cnt = 0

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

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

  def flip(self) -> None:
    self.s, self.r = self.r, self.s
    self.cnt = len(self.s) - self.cnt

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

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

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

  def toString(self) -> str:
    return ''.join(self.s)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents