DIVISION-Divisiblity by 3

Divisiblity by 3

Below given c++ code for division spoj or Divisiblity by 3 spoj.

First see the divisibility of number ‘X’ by three when written in binary form .

A binary number is a multiple of 3 if and only if the alternating sum of its bits is also a multiple of 3

let see for some ‘X’:-

4   = 100       1 - 0 + 0 = 1, not multiple of 3

6   = 110       1 - 1 + 0 = 0, multiple of 3

78  = 1001110   1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3

109 = 1101101   1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3

Now we have to find how many numbers exist in decimal form(base 10) such that when converted into binary(base 2) form has N length and is divisible by 3.(I will call this n as binary length)

Now let’s start with length N=1;

N=1 = 0 ->divisible by 3  total = 1;

N=2  then (00) & (11) is divisible by 3 , Total = 2;

N=3 We can see that all number of binary length less than 3 will present in it

                                            1-> 000

                                            2-> 011

                                            3-> 110

For N=3 total 3 number are possible.

Similarly we will get for all other number. Now will se how to calculate it for large number ,for that we have to find relation between them. Let’s derive that ->

N=1 ->1

N=2 ->2        (2*1)

N=3 ->3        (2*1)*2 - 1

N=4 -> 6       (2^2 -1)*2

N=5 ->11      (2^3 – 2^1)*2 - 1

N=6 ->22      (2^4 – 2^2 -1) *2

N=7 ->43      (2^5 – 2^3 – 2^1)*2 - 1

From the above we can find out that if ‘N’ is even then:-

Total number divisible by three will be given by->   2^n-1  - (2 + 2³ + 2⁵ +…….+ 2^n-3)

Similarly for odd one-> 2^n-1  - (1+2 + 2³ + 2⁵ +…….+ 2^n-3)

On reducing the above we will get

For EVEV ->  (2ⁿ + 2)/3

ODD -> (2ⁿ + 1)/3

Hence our complexity reduces to O(log n) because we can find (a^b MOD P) in logarithmic time. 

#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long 
#define MOD 1000000007
#define INV 333333336 //Inverse modulo of 3 with 1000000007
ULL pow_mod(ULL n)
{
    ULL x=1,p=2;
    while(n)
    {
        if(n&1)
            x=(x*p)%MOD;
        p=(p*p)%MOD;
        n>>=1;
    }
    return x;
}
int main()
{
    ULL n,result;
    while(scanf("%llu",&n)!=EOF)
    {
        if(n&1){
            result = ((pow_mod(n)+1)*INV)%MOD;
            printf("%llu\n",result);
        }
        else{
            result = ((pow_mod(n)+2)*INV)%MOD;
            printf("%llu\n",result);
        }
    }
    return 0;
}