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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class DivisibleThreeStream {
   public:
   DivisibleThreeStream(): val(0) {
 
   }
 
   bool takeBit(int bit) {
      val = (val << 1) + (bit & 1);
      return val % 3 == 0;
   }
 
   private:
   int val;
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class DivisibleThreeStream {
   public:
   DivisibleThreeStream(): rem(0) {
 
   }
 
   bool takeBit(int bit) {
      rem = ((rem << 1) + (bit & 1)) % 3;
      return rem == 0;
   }
 
   private:
   int rem;
}

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!

–EOF (The Ultimate Computing & Technology Blog) —