Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com
And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Monday, June 30, 2014

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->   2n-1  - (2 + 23 + 25 +…….+ 2n-3)

Similarly for odd one-> 2n-1  - (1+2 + 23 + 25 +…….+ 2n-3)

On reducing the above we will get

For EVEV ->  (2n + 2)/3
ODD -> (2n + 1)/3

Hence our complexity reduces to O(log n) because we can find (ab 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;
}