LintCode: Binary Stream

Binary Stream

Similar Problems:

• Tag: #bitmanipulation, #inspiring

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:

// Blog link: 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
}