Problem


Key Idea

All operations can be done in \(O(1)\) time.

  • n: size
  • cnt: number of 1’s
  • flipped: check if it’s flipped ⭐️
  • bitset: vector array of bits
  • orig: to_string() value of bitset
  • comp: to_string() value of flipped bitset

fix(idx):

if that bit needs flip,
increment cnt
flip bitset[idx], orig[idx], comp[idx]

unfix(idx):

if that bit needs flip,
decrement cnt
flip bitset[idx], orig[idx], comp[idx]

flip():

cnt = n-cnt
flipped = flipped ^ 1

all():

return cnt == n

one():

return cnt > 0

count():

return cnt

toString():

return flipped ? comp : orig


Implementation

/**
 * written: 2022. 02. 11. Fri. 17:41:01 [UTC+9]
 * jooncco의 mac에서.
 **/

typedef vector<int> vi;

class Bitset {
private:
    int n, cnt, flipped;
    vi bitset;
    string orig, comp;
    
public:
    Bitset(int size) {
        n= size;
        cnt= flipped= 0;
        bitset= vi(size,0);$
        orig= string(size,'0');
        comp= string(size,'1');
    }
    
    void fix(int idx) {
        // need flip ?
        if ((bitset[idx]^flipped) == 0) {
            ++cnt;
            bitset[idx] ^= 1;
            orig[idx]= (char)(((orig[idx]-'0') ^ 1) + '0');
            comp[idx]= (char)(((comp[idx]-'0') ^ 1) + '0');
        }
    }
    
    void unfix(int idx) {
        // need flip ?
        if ((bitset[idx]^flipped) == 1) {
            --cnt;
            bitset[idx] ^= 1;
            orig[idx]= (char)(((orig[idx]-'0') ^ 1) + '0');
            comp[idx]= (char)(((comp[idx]-'0') ^ 1) + '0');
        }
    }
    
    void flip() {
        cnt= n-cnt;
        flipped ^= 1;
    }
    
    bool all() {
        return cnt == n;
    }
    
    bool one() {
        return cnt > 0;
    }
    
    int count() {
        return cnt;
    }
    
    string toString() {
        return flipped ? comp : orig;
    }
};

  • Time: \(O(1)\)
  • Space: \(O(size)\)

Leave a comment