Design Bitset - Practice Coding Problems

Design Bitset - 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 ith index should coincide with the value at the ith bit of the Bitset.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"], values = [[2], [1], [1], [], [], [0], [], [], [0], [], []]

› Output: [null, null, null, null, false, null, null, true, null, 1, "01"]

💡 Note: Create size 2 bitset "00" → fix(1) → "01" → flip() → "10" → all() false → unfix(0) → "00" → flip() → "11" → one() true → unfix(0) → "01" → count() 1 → toString() "01"

Example 2 — All Bits Set

$ Input: operations = ["Bitset", "fix", "fix", "all", "one", "count"], values = [[2], [0], [1], [], [], []]

› Output: [null, null, null, true, true, 2]

💡 Note: Create "00" → fix(0) → "10" → fix(1) → "11" → all() true, one() true, count() 2

Example 3 — Empty Bitset

$ Input: operations = ["Bitset", "all", "one", "count", "toString"], values = [[3], [], [], [], []]

› Output: [null, false, false, 0, "000"]

💡 Note: Create size 3 bitset with all zeros: all() false, one() false, count() 0, toString() "000"

Constraints

1 ≤ size ≤ 10⁵
0 ≤ idx ≤ size - 1
At most 10⁵ calls will be made to fix, unfix, flip, all, one, count, and toString

Visualization

Tap to expand

Understanding the Visualization

Initialize

Create bitset with size n, all bits set to 0

Operations

Fix, unfix, flip bits and query status

Output

Return query results and string representation

Key Takeaway

🎯 Key Insight: Use flip flag and count tracking to make operations efficient

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is using a flip flag to avoid expensive O(n) flip operations. The optimal approach maintains a flip state and count of set bits, making all operations except toString() run in O(1) time. Time: O(1) for most operations, Space: O(n) for storing bits.

Common Approaches

Approach	Time	Space	Notes
✓ Direct Array Implementation	O(n)	O(n)	Store bits in array and perform operations directly
Flip Flag Optimization	O(1)	O(n)	Use flip flag to avoid expensive flip operations

Direct Array Implementation — Algorithm Steps

Store bits in boolean array
Implement each operation by modifying array directly
For queries, scan array when needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create array of size n with all 0s

Operations

Directly modify array elements

Flip

Scan entire array to flip each bit

Code -

solution.c — C

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

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

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

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

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

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

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

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

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

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

int main() {
    printf("[null,null,null,true,false,1,\"01\"]");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Flip operation requires scanning entire array of n bits

✓ Linear Growth

Space Complexity

O(n)

Array stores n boolean values

⚡ Linearithmic Space

15.4K Views

Medium Frequency

~25 min Avg. Time

289 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Array Implementation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler