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 <= 1050 <= idx <= size - 1105 calls will be made in total to fix, unfix, flip, all, one, count, and toString.all, one, count, or toString.5 calls will be made to toString.Problem Overview: Design a data structure that represents a binary bitset of size n. The structure must support operations like fix, unfix, flip, all, one, count, and toString. Each operation should update or query the bitset efficiently while maintaining correct counts of 0s and 1s.
Approach 1: Array-based Manipulation (O(1) per operation, O(n) flip)
Store the bitset directly in an array or string-like structure where each index represents a bit. Operations like fix(i) and unfix(i) simply update the value at index i and adjust a running counter of 1s. Queries like all(), one(), and count() read from this counter, so they run in constant time. The expensive operation is flip(), which requires iterating through the entire array and toggling every bit, giving O(n) time while other operations remain O(1). Space complexity is O(n) for storing the bitset. This approach is straightforward and easy to implement using basic array operations.
Approach 2: Optimized Lazy Flip with Counters (O(1) per operation)
The key observation is that physically flipping every bit is unnecessary. Instead, maintain a boolean flipped flag that represents whether the logical bitset is inverted. When the flag is true, the stored bit value means the opposite of what it normally represents. The fix and unfix operations interpret the current value using this flag and update the underlying array accordingly. Maintain a running count of 1s so count(), all(), and one() remain constant time. The flip() operation simply toggles the flag and recalculates the number of 1s as n - count, avoiding any iteration. Every operation runs in O(1) time with O(n) space. This technique is common in design problems where you defer expensive work until necessary.
The toString() method constructs the output by iterating through the stored array and applying the flip logic if needed. This step takes O(n) time, which is unavoidable since the full string must be produced. Implementation typically uses arrays or mutable strings, and the logic resembles techniques used in string manipulation tasks.
Recommended for interviews: Interviewers expect the lazy flip design. The naive array approach shows you understand the required operations, but the optimized version demonstrates strong system design thinking. Avoiding repeated O(n) flips and maintaining counters for constant-time queries shows the ability to optimize state-heavy data structures.
In this approach, we use a simple array to track the state of each bit in the Bitset. Operations like fix and unfix directly update this array, while flipping involves inverting each bit in the array. The overhead for each operation is straightforward but may require full traversal for some methods like flip.
This solution uses a straightforward approach of maintaining an array representing the bitset. Each bit's state can be modified using simple index operations. To implement flip, each bit is iterated and inverted. The operations of fix, unfix, and flip all work in O(n) time, while count and toString iterate over the array to compile results or construct strings from the array.
Time complexity: O(n) for operations like flip and toString;
Space complexity: O(n) for storing the bits array.
This approach optimizes the flip operation by using a lazy strategy. We maintain a 'flipped' boolean alongside the bitset to track the flip state. Instead of flipping bits immediately, we interpret bit values conditioned on the flip state. Additional counters track the number of 1s and handle state adjustments efficiently.
This optimized approach maintains a flipped state and conditionally adjusts each operation to reflect this state. By tracking 'flipped', operations like flip become O(1), as the actual bit inversion calculation is deferred. A counter, onesCount, tracks the number of 1s, aiding direct implementation of all, one, and count methods.
C++
Java
Python
JavaScript
Time complexity: O(1) for most operations, O(n) for toString due to construction;
Space complexity: O(n) for storing bit representations.
| Approach | Complexity |
|---|---|
| Array-based Manipulation | Time complexity: O(n) for operations like flip and toString; |
| Optimized Lazy Flip with Counters | Time complexity: O(1) for most operations, O(n) for toString due to construction; |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array-based Manipulation | O(1) operations, O(n) flip | O(n) | Simple implementation when performance of flip is not critical |
| Lazy Flip with Counters | O(1) per operation | O(n) | Preferred for interviews and large inputs where repeated flips would be expensive |
花花酱 LeetCode 2166. Design Bitset - 刷题找工作 EP399 • Hua Hua • 1,498 views views
Watch 8 more video solutions →Practice Design Bitset with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor