Design a Binary-Integer-Divisble-By-Three Stream using Math

Let’s design a data stream that takes a bit either 1 or 0, and then returns true/false to indicate that the integer (constructed by the bits so far) is divisible by three or not.

For example:
Take 1 – False as 1 is not divisble by three.
Take 1 – Yes, as 11 in Binary is Three which is divisble by three.
Take 0 – Yes, as 110 in Binary is Six which is disible by three.

Naive Stream to Check if Value is Divisble by Three

We can store the current number in the system – and checking the divisbility-by-three at realtime. However, it would not be practical to store ever-growing numbers as each time a new bit is added to the stream, the number doubles (multiply by two).

class DivisibleThreeStream {
   public:
   DivisibleThreeStream(): val(0) {

   }

   bool takeBit(int bit) {
      val = (val << 1) + (bit & 1);
      return val % 3 == 0;
   }

   private:
   int val;
}

Everytime we take a new bit – we shift the existing value one position to the left (which is virtually multiplying by two) and add the current bit, then return its divisibility by three.

Check if Value is Divisble by Three by using Math

In fact, we don’t need to store the value but its remainder. The remainder gets doubled everytime.

class DivisibleThreeStream {
   public:
   DivisibleThreeStream(): rem(0) {

   }

   bool takeBit(int bit) {
      rem = ((rem << 1) + (bit & 1)) % 3;
      return rem == 0;
   }

   private:
   int rem;
}

This problem can also be solved using the state machine – stay tuned!

Math

• Understanding the Sigma Function: Divisors, Multiplicativity, and the Formula
• Toss a Coin 256 Times: The Math Behind an Unbreakable Bitcoin Private Key
• Fundamental Mathematical Formulas for Machine Learning Optimization: Argmax & Reasoning Backward from the Future
• Tetration Operator in Math Simply Explained with Python Algorithms
• ChatGPT-4 uses Math Wolfram Plugin to Solve a Math Brain Teaser Question
• Bash Script to Compute the Math Pi Constant via Monte Carlo Simulation
• Design a Binary Integer Divisble by Three Stream Using Math

–EOF (The Ultimate Computing & Technology Blog) —