Binary string remainder 3

Question

-How to find x mod 3 when x is binary number? Not allowed to use conversion to decimal and then using % operator.

-eg- if x is 1101 then output should be 1 but do not convert 1101 to 13 and then find by % 3

Answer 1

Since you said "string", I'll add the following technique:

Note that if you append 0 at the end of a binary number, you double it's value. If you append 1 at the end, you double it and add 1.

That is, if you have processed all digits up to a certain digit (call this number up to that digit a), and you know that a % 3 = x for some x=1, 2 or 0, then you can tell the following:

a0 % 3 = (2 * a) % 3 = ((2 % 3) * (a % 3)) % 3 = (2 * (a % 3)) % 3
a1 % 3 = (2 * a + 1) % 3 = ((2 % 3) * (a % 3) + (1 % 3)) % 3 = (2 * (a % 3) + 1) % 3

This way, you can easily make the following distinction:

Current mod | Next digit | New mod
------------+------------+---------
   0            0            0
   0            1            1
   1            0            2
   1            1            0
   2            0            1
   2            1            2

That is, you can traverse your string from left to right (assuming msbf notation) and update the new mod according to the table. You start with current mod = 0.

Answer 2

it's very fast and innovative.

3 in binary is 11 i.e. 11 in base 10. So we know a number is divisible by 11, if the difference of the sum of digits at odd places and the sum of its digits at even places, is either 0 or divisible by 11.

So add the even placed 1s and add the odd placed 1. Take difference. Please check the below program, we are doing exactly same thing. If you have string same also applies.

public static boolean isDivisible(int n){
    if(n<0){
        n=-n;
    }
    if(n==0)return true;
    if(n==1)return false;
    int even=0, odd=0;
    while(n!=0){
        if((n&1)==1){
            odd++;
        }
        n=n>>1;
        if(n==0)break;
        if((n&1)==1){
            even++;
        }
    }
    return isDivisible(even-odd);
}

For more you can follow this and this.