2166. 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.

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^5
0 <= idx <= size - 1
At most 10^5 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.

Problem Summary #

A Bitset is a data structure that can store bits in a compact form.

Please 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 index idx to 1. If the value is already 1, no change occurs.
void unfix(int idx) updates the value of the bit at index idx to 0. If the value is already 0, no change occurs.
void flip() flips the value of every bit in the Bitset. In other words, all bits with value 0 will become 1, and vice versa.
boolean all() checks whether the value of every bit in the Bitset is 1. If this condition is satisfied, return true; otherwise, return false.
boolean one() checks whether at least one bit in the Bitset has value 1. If this condition is satisfied, return true; otherwise, return false.
int count() returns the total number of bits in the Bitset whose value is 1.
String toString() returns the current composition of the Bitset. Note that in the result string, the character at the ith index should match the ith bit in the Bitset.

Notes:

1 <= size <= 10^5
0 <= idx <= size - 1
At most 10^5 calls will be made in total to the fix, unfix, flip, all, one, count, and toString methods
At least one call will be made to the all, one, count, or toString method
At most 5 calls will be made to the toString method

Solution Approach #

The problem gives a size of 10^5 binary bits, so an int64 data type cannot be used.
Use arrays to simulate a series of operations on binary bits. The flip operation does not need to actually flip every bit each time. An even number of flips is equivalent to no flip, while an odd number of flips can be recorded with a marker, and the number of 1s is updated at the same time. This lazy operation is applied to the original array when fix and unfix are called.
fix and unfix update the binary bit according to the marker in the lazy array. At the same time, update the number of 1s.
all, one, and count are all determined by the number of 1s. toString just outputs the result.

Code #

package leetcode

type Bitset struct {
	set      []byte
	flipped  []byte
	oneCount int
	size     int
}

func Constructor(size int) Bitset {
	set := make([]byte, size)
	flipped := make([]byte, size)
	for i := 0; i < size; i++ {
		set[i] = byte('0')
		flipped[i] = byte('1')
	}
	return Bitset{
		set:      set,
		flipped:  flipped,
		oneCount: 0,
		size:     size,
	}
}

func (this *Bitset) Fix(idx int) {
	if this.set[idx] == byte('0') {
		this.set[idx] = byte('1')
		this.flipped[idx] = byte('0')
		this.oneCount++
	}
}

func (this *Bitset) Unfix(idx int) {
	if this.set[idx] == byte('1') {
		this.set[idx] = byte('0')
		this.flipped[idx] = byte('1')
		this.oneCount--
	}
}

func (this *Bitset) Flip() {
	this.set, this.flipped = this.flipped, this.set
	this.oneCount = this.size - this.oneCount
}

func (this *Bitset) All() bool {
	return this.oneCount == this.size
}

func (this *Bitset) One() bool {
	return this.oneCount != 0
}

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

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

/**
 * 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();
 */