1

A infinitely long stream of 0's and 1's are coming ,you have to find out whether number formed so far is divisible by 3 or not.

i tried it by finding decimal equivalent of binary number and then summing all the digits and finding if that sum is divisible by 3 or not. but i know it is wrong method because number is infinitely long so after some time number will be out of range. So what would be the approach for this.

another approach would be to find out even positions set bits and odd positions set bits and if difference of total number of set bits for odd and even positions is divisible by 3 then number will be divisible by 3. but here also after sum time number will be out of range.

is there any better approach?

Ankit Rathore
  • 78
  • 2
  • 10
  • possible duplicate of [Check if a number is divisible by 3](http://stackoverflow.com/questions/844867/check-if-a-number-is-divisible-by-3) (at least I think it is, that question is a bit cryptic IMO) – Bernhard Barker Aug 19 '15 at 18:08

1 Answers1

2

Just keep track of x = current number mod 3.

If b is the next bit, update:

x = (2*x + b) % 3

When x = 0 the current number is divisible by 3

John Coleman
  • 51,337
  • 7
  • 54
  • 119