Problem statement

https://binarysearch.com/problems/Virtual-Boolean-Array/

Solution

Keep set of activated bits and inv which says that we need to invert all bits.

Complexity

It is O(1) for all operations for time and O(n) for space.

Code

class BooleanArray:
    def __init__(self):
        self.bits = set()
        self.inv = 0

    def setTrue(self, i):
        if not self.inv:
            self.bits.add(i)
        else:
            self.bits.discard(i)

    def setFalse(self, i):
        if not self.inv:
            self.bits.discard(i)
        else:
            self.bits.add(i)

    def setAllTrue(self):
        self.bits = set()
        self.inv = 1

    def setAllFalse(self):
        self.bits = set()
        self.inv = 0

    def getValue(self, i):
        if not self.inv:
            return i in self.bits
        else:
            return i not in self.bits