Problem statement

A bitset stores a fixed number of bits, each 0 or 1. Write the class Bitset:

• Bitset(int size) creates size bits, all 0.
• void fix(int idx) sets bit idx to 1 (no change if it already is).
• void unfix(int idx) sets bit idx to 0 (no change if it already is).
• void flip() inverts every bit: each 0 becomes 1 and each 1 becomes 0.
• boolean all() returns whether every bit is 1.
• boolean one() returns whether at least one bit is 1.
• int count() returns how many bits are 1.
• String toString() returns the bits as a string of 0s and 1s, bit 0 first.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

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: After fixing bits 3 and 1 the bitset is 01010; flip makes it 10101, so not all bits are 1. unfix(0) gives 00101 and flip gives 11010, which has a 1. unfix(0) leaves 01010: two 1s.

Example 2

Input: ["Bitset","one","flip","all","count","unfix","toString","fix","all"]
[[2],[],[],[],[],[1],[],[1],[]]
Output: [null,false,null,true,2,null,"10",null,true]
Explanation: Two zero bits: none is 1. After flip both are 1, so all() is true. unfix(1) gives 10; fixing bit 1 again makes all() true.

Constraints

• 1 <= size <= 10^5
• 0 <= idx <= size - 1
• At most 10^5 calls are made in total to fix, unfix, flip, all, one, count and toString
• At least one call is made to all, one, count or toString
• At most 5 calls are made to toString

Hints for Design Bitset

1. Hint 1

   Flipping every bit one by one costs O(size) per call, and there can be 10^5 flips. Can a flip be recorded instead of performed?

2. Hint 2

   Keep one flipped flag. The real value of bit i is stored[i] XOR flipped, so flip() only toggles the flag.

3. Hint 3

   Also keep the number of 1s. fix/unfix change it by one only when the bit's real value actually changes, and flip turns it into size - ones. Then all, one and count are O(1).

How to solve Design Bitset

Never touch the whole array on a flip: store the bits as they were last written plus a global flipped flag, and keep a running count of 1s. Every operation except toString becomes O(1).

Approach

1. Store stored[0..size-1] (all 0), flipped = 0 and ones = 0.
2. fix(idx): if stored[idx] XOR flipped is 0, toggle stored[idx] and add 1 to ones.
3. unfix(idx): if stored[idx] XOR flipped is 1, toggle stored[idx] and subtract 1 from ones.
4. flip(): toggle flipped and set ones = size - ones.
5. all() is ones == size, one() is ones > 0, count() is ones.
6. toString() writes stored[i] XOR flipped for every i.

Why it works

The invariant is that bit i equals stored[i] XOR flipped and that ones counts the indices where that is 1. fix/unfix toggle the stored bit only when the real bit must change, which changes the count by exactly one; flip inverts every real bit at once, so the 1s become exactly the former 0s, of which there were size - ones.

Complexity

• Time — O(1) per operation except toString, which is O(size)
• Space — O(size)

Pitfalls

• fix on a bit that is already 1 must not change the count — compare the real value, not the stored one.
• Build toString with a string builder; concatenating characters one at a time is quadratic in some languages.

Reference solution

Python

class Bitset:

    def __init__(self, size: int):
        self.size = size
        self.stored = [0] * size  # the real bit i is stored[i] ^ flipped
        self.flipped = 0
        self.ones = 0

    def fix(self, idx: int) -> None:
        if self.stored[idx] ^ self.flipped == 0:
            self.stored[idx] ^= 1
            self.ones += 1

    def unfix(self, idx: int) -> None:
        if self.stored[idx] ^ self.flipped == 1:
            self.stored[idx] ^= 1
            self.ones -= 1

    def flip(self) -> None:
        self.flipped ^= 1
        self.ones = self.size - self.ones

    def all(self) -> bool:
        return self.ones == self.size

    def one(self) -> bool:
        return self.ones > 0

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

    def toString(self) -> str:
        f = self.flipped
        return "".join("1" if b ^ f else "0" for b in self.stored)

Java

class Bitset {
    private boolean[] stored; // the real bit i is stored[i] ^ flipped
    private boolean flipped = false;
    private int size, ones = 0;

    public Bitset(int size) {
        this.size = size;
        stored = new boolean[size];
    }

    public void fix(int idx) {
        if (stored[idx] == flipped) { stored[idx] = !stored[idx]; ones++; }
    }

    public void unfix(int idx) {
        if (stored[idx] != flipped) { stored[idx] = !stored[idx]; ones--; }
    }

    public void flip() {
        flipped = !flipped;
        ones = size - ones;
    }

    public boolean all() { return ones == size; }

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

    public int count() { return ones; }

    public String toString() {
        StringBuilder sb = new StringBuilder(size);
        for (int i = 0; i < size; i++) sb.append(stored[i] != flipped ? '1' : '0');
        return sb.toString();
    }
}

C++

class Bitset {
    vector<char> stored; // the real bit i is stored[i] ^ flipped
    int size, ones = 0;
    char flipped = 0;
public:
    Bitset(int size) : stored(size, 0), size(size) {}

    void fix(int idx) {
        if ((stored[idx] ^ flipped) == 0) { stored[idx] ^= 1; ones++; }
    }

    void unfix(int idx) {
        if ((stored[idx] ^ flipped) == 1) { stored[idx] ^= 1; ones--; }
    }

    void flip() {
        flipped ^= 1;
        ones = size - ones;
    }

    bool all() { return ones == size; }

    bool one() { return ones > 0; }

    int count() { return ones; }

    string toString() {
        string s(size, '0');
        for (int i = 0; i < size; i++) if (stored[i] ^ flipped) s[i] = '1';
        return s;
    }
};

JavaScript

var Bitset = function(size) {
    this.size = size;
    this.stored = new Uint8Array(size); // the real bit i is stored[i] ^ flipped
    this.flipped = 0;
    this.ones = 0;
};

Bitset.prototype.fix = function(idx) {
    if ((this.stored[idx] ^ this.flipped) === 0) { this.stored[idx] ^= 1; this.ones++; }
};

Bitset.prototype.unfix = function(idx) {
    if ((this.stored[idx] ^ this.flipped) === 1) { this.stored[idx] ^= 1; this.ones--; }
};

Bitset.prototype.flip = function() {
    this.flipped ^= 1;
    this.ones = this.size - this.ones;
};

Bitset.prototype.all = function() { return this.ones === this.size; };

Bitset.prototype.one = function() { return this.ones > 0; };

Bitset.prototype.count = function() { return this.ones; };

Bitset.prototype.toString = function() {
    var parts = new Array(this.size);
    for (var i = 0; i < this.size; i++) parts[i] = (this.stored[i] ^ this.flipped) ? "1" : "0";
    return parts.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Range Frequency Queries Medium
• Simple Bank System Medium