2166 - Design Bitset (Medium)

Problem Link

https://leetcode.com/problems/design-bitset/

Problem Statement

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 <= 1e5
• 0 <= idx <= size - 1
• At most 1e5 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.

Approach 1: Class Implementation

In general, we need to keep track of 3 things:

• The state of the bits
• The number of 1s
• Flipped or not

We first consider the flip function first. The naive way to perform flip is to iterate over the bits and change all the bits. This takes $O(N)$ time and is too slow. We instead use a state called flipped to store the state whether the bits are flipped or not. When we call flip, the new number of 1s in bits becomes the old number of 0s in bits, which can be calculated by len(bits) - ones.

We then consider fix and unfix. These two functions require certain condition of the target bit to activate. If we want to check a bit is 1 or not, we have two possibilities

• target bit is 0, and flipped = True
• target bit is 1, and flipped = False

Then we update the target bit and ones accordingly.

Similar logic applies to toString that we need to accommodate the state of flipped

Written by @heiheihang

class Bitset:

    def __init__(self, size: int):

        #record the state of the bit
        self.bits = [0] * size

        #record the number of ones
        self.ones = 0

        #record if flip is called
        self.flipped = False


    def fix(self, idx: int) -> None:

        #we need to check if the target bit is 0 (if not flipped -> 0) or 1 (if flipped -> 0)
        if(self.bits[idx] == 0 and not self.flipped or self.bits[idx] == 1 and self.flipped):

            #add 1 to ones if it is 0 (after considering flip)
            self.ones += 1

            #change its state
            self.bits[idx] = (self.bits[idx] + 1) % 2


    def unfix(self, idx: int) -> None:

        #we need to check if the target bit is 1 (if not flipped -> 1) or 0 (if flipped -> 1)
        if(self.bits[idx] == 1 and not self.flipped or self.bits[idx] == 0 and self.flipped):

            #decrease 1 to ones if it is 1 (after considering flip)
            self.ones -= 1

            #change its state
            self.bits[idx] = (self.bits[idx] + 1) % 2

    #this needs to be O(1)!
    def flip(self) -> None:

        #we reverse the number of ones after flip
        self.ones = len(self.bits) - self.ones

        #update the state of flipped
        if(self.flipped):
            self.flipped = False
        else:
            self.flipped = True

    def all(self) -> bool:

        #check if number of ones equals to the length of bits
        if(self.ones == len(self.bits)):
            return True
        return False

    def one(self) -> bool:

        #check if there is at least one 1
        if(self.ones > 0):
            return True
        return False

    def count(self) -> int:

        #return the number of ones
        return self.ones

    def toString(self) -> str:

        #initialize the result
        res = []

        if(self.flipped):

            for i in range(len(self.bits)):

                #if flipped, we need to put the reverse of the bit to result
                res.append(str((self.bits[i] + 1) % 2))
        else:
            for i in range(len(self.bits)):

                #put the bit to result
                res.append(str(self.bits[i]))

        #return the string of list
        return "".join(res)