aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--design_bitset.c92
-rw-r--r--design_bitset.py106
2 files changed, 198 insertions, 0 deletions
diff --git a/design_bitset.c b/design_bitset.c
new file mode 100644
index 0000000..5363e2c
--- /dev/null
+++ b/design_bitset.c
@@ -0,0 +1,92 @@
+// 2166. Design Bitset
+#include "leetcode.h"
+
+/*
+ * a bitset is a data structure that compactly stores bits. implement the
+ * 'Bitset' class. 'Bitset(int size)' initialises the bitsetwith '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
+ * biset. 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 withvalue 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
+ */
+
+typedef struct {
+ int ones;
+ int size;
+ char *digits;
+ char *reverse;
+} Bitset;
+
+Bitset *bitsetCreate(int size) {
+ Bitset *obj = (Bitset *)malloc(sizeof(Bitset));
+ obj->ones = 0;
+ obj->size = size;
+ obj->digits = (char *)malloc((size + 1) * sizeof(char));
+ obj->reverse = (char *)malloc((size + 1) * sizeof(char));
+ memset(obj->digits, '0', size);
+ memset(obj->reverse, '1', size);
+ obj->digits[size] = '\0';
+ obj->reverse[size] = '\0';
+ return obj;
+}
+
+void bitsetFix(Bitset *obj, int idx) {
+ if (obj->digits[idx] != '1') {
+ obj->digits[idx] = '1';
+ obj->reverse[idx] = '0';
+ obj->ones++;
+ }
+}
+
+void bitsetUnfix(Bitset *obj, int idx) {
+ if (obj->digits[idx] != '0') {
+ obj->digits[idx] = '0';
+ obj->reverse[idx] = '1';
+ obj->ones--;
+ }
+}
+
+void bitsetFlip(Bitset *obj) {
+ char *tmp = obj->digits;
+ obj->digits = obj->reverse;
+ obj->reverse = tmp;
+ obj->ones = obj->size - obj->ones;
+}
+
+bool bitsetAll(Bitset *obj) { return obj->ones == obj->size; }
+
+bool bitsetOne(Bitset *obj) { return obj->ones > 0; }
+
+int bitsetCount(Bitset *obj) { return obj->ones; }
+
+char *bitsetToString(Bitset *obj) { return obj->digits; }
+
+void bitsetFree(Bitset *obj) {
+ free(obj->digits);
+ free(obj->reverse);
+ free(obj);
+}
+
+int main() {
+ Bitset *obj = bitsetCreate(5);
+ bitsetFix(obj, 3);
+ bitsetFix(obj, 1);
+ bitsetFlip(obj);
+ printf("%d\n", bitsetAll(obj)); // expect: 0
+ bitsetUnfix(obj, 0);
+ bitsetFlip(obj);
+ printf("%d\n", bitsetOne(obj)); // expect: 1
+ bitsetUnfix(obj, 0);
+ printf("%d\n", bitsetCount(obj)); // expect: 2
+ printf("%s\n", bitsetToString(obj)); // expect: 01010
+ bitsetFree(obj);
+}
diff --git a/design_bitset.py b/design_bitset.py
new file mode 100644
index 0000000..96928d1
--- /dev/null
+++ b/design_bitset.py
@@ -0,0 +1,106 @@
+# 2166. Design Bitset
+
+"""
+a bitset is a data structure that compactly stores bits. implement the
+'Bitset' class. 'Bitset(int size)' initialises the bitsetwith '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
+biset. 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 withvalue 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
+"""
+
+
+class Bitset(object):
+ def __init__(self, size):
+ """
+ :type size: int
+ """
+ self.arr = [0] * size
+ self.ones = 0
+ self.rev = False
+
+ def fix(self, idx):
+ """
+ :type idx: int
+ :rtype: None
+ """
+ if self.rev:
+ if self.arr[idx] == 1:
+ self.ones += 1
+ self.arr[idx] = 0
+ else:
+ if self.arr[idx] == 0:
+ self.ones += 1
+ self.arr[idx] = 1
+
+ def unfix(self, idx):
+ """
+ :type idx: int
+ :rtype: None
+ """
+ if self.rev:
+ if self.arr[idx] == 0:
+ self.ones -= 1
+ self.arr[idx] = 1
+ else:
+ if self.arr[idx] == 1:
+ self.ones -= 1
+ self.arr[idx] = 0
+
+ def flip(self):
+ """
+ :rtype: None
+ """
+ self.rev = not self.rev
+ self.ones = len(self.arr) - self.ones
+
+ def all(self):
+ """
+ :rtype: bool
+ """
+ return self.ones == len(self.arr)
+
+ def one(self):
+ """
+ :rtype: bool
+ """
+ return self.ones > 0
+
+ def count(self):
+ """
+ :rtype: int
+ """
+ return self.ones
+
+ def toString(self):
+ """
+ :rtype: str
+ """
+ return (
+ "".join([str(0 if i else 1) for i in self.arr])
+ if self.rev
+ else "".join([str(i) for i in self.arr])
+ )
+
+
+if __name__ == "__main__":
+ obj = Bitset(5)
+ obj.fix(3)
+ obj.fix(1)
+ obj.flip()
+ print(obj.all())
+ obj.unfix(0)
+ obj.flip()
+ print(obj.one())
+ obj.unfix(0)
+ print(obj.count())
+ print(obj.toString())