2166. Design Bitset Solution

Q: Is Design Bitset easy or hard?

Design Bitset is rated Medium because the operations themselves are simple but require careful state management. Many candidates initially implement a full flip in O(n), but the intended solution optimizes this using lazy flipping and counters.

Q: Design Bitset Python/Java solution

The solution in Python or Java typically uses a list or array to store bits, an integer counter for the number of 1s, and a boolean flip flag. Methods like fix, unfix, and flip update the array logically using the flag while keeping operations O(1).

Q: How to solve Design Bitset in O(1)?

Maintain an array for the stored bits, a boolean flag indicating whether the bitset is logically flipped, and a counter for the number of 1s. Fix and unfix operations check the flip flag before updating the underlying value. Flip simply toggles the flag and recalculates the count as n minus the current count.

Q: What is the best approach for Design Bitset?

The optimal solution uses a lazy flip technique with a boolean flag and a running count of 1s. Instead of flipping every bit, the algorithm toggles a flip flag and adjusts the count using n - count. This makes fix, unfix, flip, all, one, and count operations O(1) while keeping space complexity at O(n).

Q: Is Design Bitset asked at Google/Amazon/Meta?

Bit manipulation and custom data structure design problems appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, similar tasks involving efficient state updates and lazy operations are common in system design and algorithm rounds.

Q: What data structure is used in Design Bitset?

The core structure is an array or list storing binary values. The optimized solution augments this with a boolean flip flag and a counter tracking how many bits are set to 1. This combination allows constant-time updates and queries.

Q: What is the time complexity of Design Bitset?

With the optimized lazy flip design, all update and query operations run in O(1) time. The only O(n) operation is toString(), since it must construct the entire bitset string. Space complexity remains O(n) because the structure stores the bitset array.

The problem

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 i^th index should coincide with the value at the i^th 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 <= 10⁵
0 <= idx <= size - 1
At most 10⁵ 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 overview

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.

Approach 1: Array-based Manipulation

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.

Python


class Bitset:
    def __init__(self, size: int):
        self.bits = [0] * size
        self.size = size

    def fix(self, idx: int) -> None:
        self.bits[idx] = 1

    def unfix(self, idx: int) -> None:
        self.bits[idx] = 0

    def flip(self) -> None:
        for i in range(self.size):
            self.bits[i] = 1 - self.bits[i]

    def all(self) -> bool:
        return all(self.bits)

    def one(self) -> bool:
        return any(self.bits)

    def count(self) -> int:
        return sum(self.bits)

    def toString(self) -> str:
        return ''.join(map(str, self.bits))

Java


public class Bitset {
    private int[] bits;
    private int size;

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

    public void fix(int idx) {
        bits[idx] = 1;
    }

    public void unfix(int idx) {
        bits[idx] = 0;
    }

    public void flip() {
        for (int i = 0; i < size; i++) {
            bits[i] = 1 - bits[i];
        }
    }

    public boolean all() {
        for (int bit : bits) {
            if (bit == 0) return false;
        }
        return true;
    }

    public boolean one() {
        for (int bit : bits) {
            if (bit == 1) return true;
        }
        return false;
    }

    public int count() {
        int cnt = 0;
        for (int bit : bits) {
            cnt += bit;
        }
        return cnt;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int bit : bits) {
            sb.append(bit);
        }
        return sb.toString();
    }
}

C++


#include <vector>
#include <string>

class Bitset {
    std::vector<int> bits;
    int size;

public:
    Bitset(int size) : size(size) {
        bits.resize(size, 0);
    }

    void fix(int idx) {
        bits[idx] = 1;
    }

    void unfix(int idx) {
        bits[idx] = 0;
    }

    void flip() {
        for (int &bit : bits) {
            bit = 1 - bit;
        }
    }

    bool all() {
        for (auto bit : bits) {
            if (bit == 0) return false;
        }
        return true;
    }

    bool one() {
        for (auto bit : bits) {
            if (bit == 1) return true;
        }
        return false;
    }

    int count() {
        int cnt = 0;
        for (auto bit : bits) {
            cnt += bit;
        }
        return cnt;
    }

    std::string toString() {
        std::string result;
        for (auto bit : bits) {
            result += std::to_string(bit);
        }
        return result;
    }
};

JavaScript


class Bitset {
    constructor(size) {
        this.bits = new Array(size).fill(0);
        this.size = size;
    }

    fix(idx) {
        this.bits[idx] = 1;
    }

    unfix(idx) {
        this.bits[idx] = 0;
    }

    flip() {
        for (let i = 0; i < this.size; i++) {
            this.bits[i] = 1 - this.bits[i];
        }
    }

    all() {
        return this.bits.every(bit => bit === 1);
    }

    one() {
        return this.bits.some(bit => bit === 1);
    }

    count() {
        return this.bits.reduce((sum, bit) => sum + bit, 0);
    }

    toString() {
        return this.bits.join('');
    }
}


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int* bits;
    int size;
} Bitset;

Bitset* createBitset(int size) {
    Bitset* obj = (Bitset*)malloc(sizeof(Bitset));
    obj->bits = (int*)calloc(size, sizeof(int));
    obj->size = size;
    return obj;
}

void fix(Bitset* obj, int idx) {
    obj->bits[idx] = 1;
}

void unfix(Bitset* obj, int idx) {
    obj->bits[idx] = 0;
}

void flip(Bitset* obj) {
    for (int i = 0; i < obj->size; i++) {
        obj->bits[i] = obj->bits[i] == 0 ? 1 : 0;
    }
}

bool all(Bitset* obj) {
    for (int i = 0; i < obj->size; i++) {
        if (obj->bits[i] == 0) return false;
    }
    return true;
}

bool one(Bitset* obj) {
    for (int i = 0; i < obj->size; i++) {
        if (obj->bits[i] == 1) return true;
    }
    return false;
}

int count(Bitset* obj) {
    int cnt = 0;
    for (int i = 0; i < obj->size; i++) {
        cnt += obj->bits[i];
    }
    return cnt;
}

char* toString(Bitset* obj) {
    char* str = (char*)malloc((obj->size + 1) * sizeof(char));
    for (int i = 0; i < obj->size; i++) {
        str[i] = obj->bits[i] + '0';
    }
    str[obj->size] = '\0';
    return str;
}

void freeBitset(Bitset* obj) {
    free(obj->bits);
    free(obj);
}


using System;
using System.Text;

public class Bitset {
    private int[] bits;
    private int size;

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

    public void Fix(int idx) {
        bits[idx] = 1;
    }

    public void Unfix(int idx) {
        bits[idx] = 0;
    }

    public void Flip() {
        for (int i = 0; i < size; i++) {
            bits[i] = 1 - bits[i];
        }
    }

    public bool All() {
        foreach (int bit in bits) {
            if (bit == 0) return false;
        }
        return true;
    }

    public bool One() {
        foreach (int bit in bits) {
            if (bit == 1) return true;
        }
        return false;
    }

    public int Count() {
        int cnt = 0;
        foreach (int bit in bits) {
            cnt += bit;
        }
        return cnt;
    }

    public string ToString() {
        StringBuilder sb = new StringBuilder();
        foreach (int bit in bits) {
            sb.Append(bit);
        }
        return sb.ToString();
    }
}

Python provides rich built-in support for list operations making the manipulation of the bitset straightforward using list comprehensions and functional programming concepts like map and filter for operations. The solution is direct and Pythonic, providing clarity and simplicity.

Complexity

Time complexity: O(n) for operations like flip and toString;
Space complexity: O(n) for storing the bits list.

Try this approach in the editor

Approach 2: Optimized Lazy Flip with Counters

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.

Python


class Bitset:
    def __init__(self, size: int):
        self.bits = [0] * size
        self.size = size
        self.flipped = False
        self.ones_count = 0

    def fix(self, idx: int) -> None:
        if (self.bits[idx] == 0 and not self.flipped) or (self.bits[idx] == 1 and self.flipped):
            self.bits[idx] = 0 if self.flipped else 1
            self.ones_count += 1

    def unfix(self, idx: int) -> None:
        if (self.bits[idx] == 1 and not self.flipped) or (self.bits[idx] == 0 and self.flipped):
            self.bits[idx] = 1 if self.flipped else 0
            self.ones_count -= 1

    def flip(self) -> None:
        self.flipped = not self.flipped
        self.ones_count = self.size - self.ones_count

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

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

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

    def toString(self) -> str:
        return ''.join(str(1 - b if self.flipped else b) for b in self.bits)

Java


public class Bitset {
    private int[] bits;
    private int size;
    private boolean flipped;
    private int onesCount;

    public Bitset(int size) {
        this.size = size;
        this.bits = new int[size];
        this.flipped = false;
        this.onesCount = 0;
    }

    public void fix(int idx) {
        if ((bits[idx] == 0 && !flipped) || (bits[idx] == 1 && flipped)) {
            bits[idx] = flipped ? 0 : 1;
            onesCount++;
        }
    }

    public void unfix(int idx) {
        if ((bits[idx] == 1 && !flipped) || (bits[idx] == 0 && flipped)) {
            bits[idx] = flipped ? 1 : 0;
            onesCount--;
        }
    }

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

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

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

    public int count() {
        return onesCount;
    }

    public String toString() {
        StringBuilder result = new StringBuilder(size);
        for (int bit : bits) {
            if (flipped) bit = 1 - bit;
            result.append(bit);
        }
        return result.toString();
    }
}

C++


class Bitset {
    std::vector<int> bits;
    int size;
    bool flipped;
    int onesCount;

public:
    Bitset(int size) : size(size), flipped(false), onesCount(0) {
        bits.resize(size, 0);
    }

    void fix(int idx) {
        if ((bits[idx] == 0 && !flipped) || (bits[idx] == 1 && flipped)) {
            bits[idx] = flipped ? 0 : 1;
            onesCount++;
        }
    }

    void unfix(int idx) {
        if ((bits[idx] == 1 && !flipped) || (bits[idx] == 0 && flipped)) {
            bits[idx] = flipped ? 1 : 0;
            onesCount--;
        }
    }

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

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

    bool one() {
        return onesCount > 0;
    }

    int count() {
        return onesCount;
    }

    std::string toString() {
        std::string result;
        for (int bit : bits) {
            if (flipped) bit = 1 - bit;
            result += '0' + bit;
        }
        return result;
    }
};

JavaScript


class Bitset {
    constructor(size) {
        this.bits = Array(size).fill(0);
        this.size = size;
        this.flipped = false;
        this.onesCount = 0;
    }

    fix(idx) {
        if ((this.bits[idx] === 0 && !this.flipped) || (this.bits[idx] === 1 && this.flipped)) {
            this.bits[idx] = this.flipped ? 0 : 1;
            this.onesCount++;
        }
    }

    unfix(idx) {
        if ((this.bits[idx] === 1 && !this.flipped) || (this.bits[idx] === 0 && this.flipped)) {
            this.bits[idx] = this.flipped ? 1 : 0;
            this.onesCount--;
        }
    }

    flip() {
        this.flipped = !this.flipped;
        this.onesCount = this.size - this.onesCount;
    }

    all() {
        return this.onesCount === this.size;
    }

    one() {
        return this.onesCount > 0;
    }

    count() {
        return this.onesCount;
    }

    toString() {
        return this.bits.map(bit => this.flipped ? 1 - bit : bit).join('');
    }
}

In the Python solution, we handle the state tracking with a flip flag and ones_count variable. The implementation ensures all operations are efficiently processed with minimal flipping required on the data itself while still supporting state updates through fix and unfix in O(1). The toString function accounts for flip state when constructing the return string.

Complexity

Time complexity: O(1) for most operations, O(n) for toString due to string construction;
Space complexity: O(n).

Try this approach in the editor

Approach 3: Default Approach

type Bitset struct {
	a   []byte
	b   []byte
	cnt int
}

func Constructor(size int) Bitset {
	a := bytes.Repeat([]byte{'0'}, size)
	b := bytes.Repeat([]byte{'1'}, size)
	return Bitset{a, b, 0}
}

func (this *Bitset) Fix(idx int) {
	if this.a[idx] == '0' {
		this.a[idx] = '1'
		this.cnt++
	}
	this.b[idx] = '0'
}

func (this *Bitset) Unfix(idx int) {
	if this.a[idx] == '1' {
		this.a[idx] = '0'
		this.cnt--
	}
	this.b[idx] = '1'
}

func (this *Bitset) Flip() {
	this.a, this.b = this.b, this.a
	this.cnt = len(this.a) - this.cnt
}

func (this *Bitset) All() bool {
	return this.cnt == len(this.a)
}

func (this *Bitset) One() bool {
	return this.cnt > 0
}

func (this *Bitset) Count() int {
	return this.cnt
}

func (this *Bitset) ToString() string {
	return string(this.a)
}

/**
 * Your Bitset object will be instantiated and called as such:
 * obj := Constructor(size);
 * obj.Fix(idx);
 * obj.Unfix(idx);
 * obj.Flip();
 * param_4 := obj.All();
 * param_5 := obj.One();
 * param_6 := obj.Count();
 * param_7 := obj.ToString();
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Array-based Manipulation	Time complexity: O(n) for operations like flip and toString; Space complexity: O(n) for storing the bits list.
Optimized Lazy Flip with Counters	Time complexity: O(1) for most operations, O(n) for toString due to string construction; Space complexity: O(n).
Default Approach	–

Complexity analysis

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

Frequently asked questions

Is Design Bitset easy or hard?

Design Bitset is rated Medium because the operations themselves are simple but require careful state management. Many candidates initially implement a full flip in O(n), but the intended solution optimizes this using lazy flipping and counters.

Design Bitset Python/Java solution

The solution in Python or Java typically uses a list or array to store bits, an integer counter for the number of 1s, and a boolean flip flag. Methods like fix, unfix, and flip update the array logically using the flag while keeping operations O(1).

How to solve Design Bitset in O(1)?

Maintain an array for the stored bits, a boolean flag indicating whether the bitset is logically flipped, and a counter for the number of 1s. Fix and unfix operations check the flip flag before updating the underlying value. Flip simply toggles the flag and recalculates the count as n minus the current count.

What is the best approach for Design Bitset?

The optimal solution uses a lazy flip technique with a boolean flag and a running count of 1s. Instead of flipping every bit, the algorithm toggles a flip flag and adjusts the count using n - count. This makes fix, unfix, flip, all, one, and count operations O(1) while keeping space complexity at O(n).

Is Design Bitset asked at Google/Amazon/Meta?

Bit manipulation and custom data structure design problems appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, similar tasks involving efficient state updates and lazy operations are common in system design and algorithm rounds.

What data structure is used in Design Bitset?

The core structure is an array or list storing binary values. The optimized solution augments this with a boolean flip flag and a counter tracking how many bits are set to 1. This combination allows constant-time updates and queries.

What is the time complexity of Design Bitset?

With the optimized lazy flip design, all update and query operations run in O(1) time. The only O(n) operation is toString(), since it must construct the entire bitset string. Space complexity remains O(n) because the structure stores the bitset array.

Design Bitset solution and explanation

The problem

Approach overview

Approach 1: Array-based Manipulation

Approach 2: Optimized Lazy Flip with Counters

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design Bitset solution and explanation

The problem

Approach overview

Approach 1: Array-based Manipulation

Approach 2: Optimized Lazy Flip with Counters

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems