Binary Stream
Similar Problems:
Description
Take each bit from a binary stream (0/1) to form a binary string. The i-th time can take consecutive i-bits from the stream. Each time a bit is taken out, the binary string consisting of the previous bits is shifted to the highest position by one bit, and then the current bit is added. When j bits (j<=i) are taken, if the value of the current binary string is divisible by 3, then output it.
The length of the binary stream is less than or equal to 200000
Example
Give a = “11011”, return [2,3,5].
Explanation: When taking 2 bits, the binary string is 11, and after converting to decimal, it is 3, which can be divisible by 3. When taking 3 bits, the binary string is 110, and after converting to decimal, it is 6, which can be divisible by 3. When taking 5 bits, the binary string is 11011, and after converting to decimal, it is 27, which can be divisible by 3.
Give a =”0000” , return [1,2,3,4].
Explanation: No matter how many bits are taken, they are all 0, so all output.
Github: code.dennyzhang.com
Credits To: lintcode.com
Leave me comments, if you have better ways to solve.
- Solution:
// https://code.dennyzhang.com/binary-stream
// Basic Ideas: binary manipulation
// Complexity: Time O(1), Space O(1)
/**
* @param s: the binary stream
* @return: the outputs
*/
func getOutput (s string) []int {
res := []int{}
val := 0
for i, ch := range s {
val = (2*val) % 3
if ch == '1' { val++ }
if val % 3 == 0 {
res = append(res, i+1)
}
}
return res
}
