Skip to content

2166. Design Bitset 👍

  • Time:
    • Constructor: $O(|\texttt{size}|)$
    • fix(idx: int): $O(1)$
    • unfix(idx: int): $O(1)$
    • flip(): $O(1)$
    • all(): $O(1)$
    • one(): $O(1)$
    • count(): $O(1)$
    • toString(): $O(1)$
  • Space: $O(|\texttt{size}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Bitset {
 public:
  Bitset(int size) : s(size, '0'), r(size, '1') {}

  void fix(int idx) {
    if (s[idx] == '0')
      ++cnt;
    s[idx] = '1';
    r[idx] = '0';
  }

  void unfix(int idx) {
    if (s[idx] == '1')
      --cnt;
    s[idx] = '0';
    r[idx] = '1';
  }

  void flip() {
    swap(s, r);
    cnt = s.length() - cnt;
  }

  bool all() {
    return cnt == s.length();
  }

  bool one() {
    return cnt;
  }

  int count() {
    return cnt;
  }

  string toString() {
    return s;
  }

 private:
  string s;  // the original
  string r;  // the reversed
  int cnt = 0;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Bitset {
  public Bitset(int size) {
    for (int i = 0; i < size; ++i) {
      sb.append('0');
      rb.append('1');
    }
  }

  public void fix(int idx) {
    if (sb.charAt(idx) == '0')
      ++cnt;
    sb.setCharAt(idx, '1');
    rb.setCharAt(idx, '0');
  }

  public void unfix(int idx) {
    if (sb.charAt(idx) == '1')
      --cnt;
    sb.setCharAt(idx, '0');
    rb.setCharAt(idx, '1');
  }

  public void flip() {
    StringBuilder temp = sb;
    sb = rb;
    rb = temp;
    cnt = sb.length() - cnt;
  }

  public boolean all() {
    return cnt == sb.length();
  }

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

  public int count() {
    return cnt;
  }

  public String toString() {
    return sb.toString();
  }

  private StringBuilder sb = new StringBuilder(); // the original
  private StringBuilder rb = new StringBuilder(); // the reversed
  private int cnt = 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Bitset:
  def __init__(self, size: int):
    self.s = ['0'] * size  # the original
    self.r = ['1'] * size  # the reversed
    self.cnt = 0

  def fix(self, idx: int) -> None:
    if self.s[idx] == '0':
      self.cnt += 1
    self.s[idx] = '1'
    self.r[idx] = '0'

  def unfix(self, idx: int) -> None:
    if self.s[idx] == '1':
      self.cnt -= 1
    self.s[idx] = '0'
    self.r[idx] = '1'

  def flip(self) -> None:
    self.s, self.r = self.r, self.s
    self.cnt = len(self.s) - self.cnt

  def all(self) -> bool:
    return self.cnt == len(self.s)

  def one(self) -> bool:
    return self.cnt

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

  def toString(self) -> str:
    return ''.join(self.s)