LintCode: Binary Stream Posted on August 18, 2018September 23, 2019 by braindenny Binary Stream Similar Problems: CheatSheet: Leetcode For Code Interview 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: // 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 } Post Views: 3