check the divisibility by 13 of a binary number

Question

how to check if a binary number is divisible 13 if the user inputs the digits from the most significant to the least significant?

the number of bits can be very large,so there is no point converting it into decimal and then checking its divisibility.

i have approached it in the conventional way. nuber of bits range upto 10^5, so it is giving overflow while converting it into decimal.

how to approach this? example:

110010000100100 it is div by 13

111111111111111 it is not divisible by 13

Answer 1

Here is an O(N) algorithm:

Traverse the bits from left to right. Each additional position is equivalent to multiplying the current value by 2, and then adding either 0 or 1. This is also true in modulo-13 arithmetic. When you get to the last bit, see if the final value is equal to 0. If it is, then the original number was divisible by 13.