Dividing Binary by Five
A computer receives a series of binary digits (1s and 0s)
representing a large number. Devise an algorithm that can decide after
each bit if the number accumulated so far is divisible by 5. You cannot
simply divide by 5 because you do not have infinite storage to store the
incoming bit stream.
The first bit received is the least significant bit,
and each following bit represents the next larger power of 2 in the large
The first bit received is the most significant bit, and
each following be represents the next lower power of 2 in the large number.
Can either of these situations be easily extended to
decide divisibility by other values (i.e. 10, 13, 100)?
Source: 1. Emanuel Manasci, citing a past interview question. 2&3. Original Extensions.
Mail to Ken