{x}
blog image

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.

Solution Explanation

This problem requires designing a Bitset class that efficiently manages a sequence of bits. The solution presented uses two arrays, a and b, to optimize the flip operation.

Data Structures:

  • a: Represents the current state of the bitset. Initially, all bits are 0.
  • b: Represents the inverted state of the bitset. Initially, all bits are 1.
  • cnt: Keeps track of the number of 1s in the bitset a. This significantly speeds up count, all, and one operations.

Time Complexity Analysis:

  • __init__(size): O(N), where N is the size of the bitset. This is due to initializing the arrays a and b.
  • fix(idx): O(1). Updating a single bit and incrementing cnt are constant time operations.
  • unfix(idx): O(1). Similar to fix.
  • flip(): O(1). Swapping the references to a and b and updating cnt takes constant time. It does not involve iterating through the entire bitset.
  • all(): O(1). Checking if cnt equals the size of the bitset is a constant time operation.
  • one(): O(1). Checking if cnt is greater than 0 is a constant time operation.
  • count(): O(1). Returning cnt is a constant time operation.
  • toString(): O(N). Converting the array a to a string involves iterating through all elements.

Space Complexity Analysis:

  • O(N), where N is the size of the bitset, due to storing the arrays a and b.

Code Explanation (Python Example):

The Python code directly implements the logic described above. Each method performs the specific operation as detailed in the problem description. The cnt variable ensures that the counting operations are very efficient. Note that the flip operation swaps the references to a and b rather than iterating and flipping each bit individually, achieving O(1) time complexity.

Other Languages:

The Java, C++, and Go code implement the same logic, adapting the syntax and data structures to the respective languages. The core concepts and time/space complexity remain the same across all implementations. For example, in Java, char[] arrays are used instead of Python lists, and similar optimizations are employed. The overall approach to handling the bitset remains consistent across all the provided solutions.