Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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
}
linkedin
github
slack

Post Views: 3
Posted in MediumTagged #bitmanipulation, #inspiring

Post navigation

LintCode: Minimum Difference
LintCode: Social Network

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #misc #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum baseconversion binarysearch concurrency editdistance hashmap knapsack monotone oodesign presum redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • Leetcode: Palindrome Partitioning III
  • Leetcode: Biggest Single Number
  • Leetcode: Max Consecutive Ones II
  • Leetcode: Minimum Cost to Connect Sticks
  • Leetcode: Minimum Swaps to Group All 1’s Together

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.