## Tuesday, 25 March 2014

### Fastest Way to check divisibility by 3

When the number is small directly check its divisibility by 3 by dividing it . works fine but if number is large this technique is no more best technique to check divisibility ..

Other way is by checking divisibility of sum of its digit . but this technique is also not effective because to find each digit we need to divide again & again by 10.

But there exist a much faster way to check this .

Now think about binary representation of a number in binary . Since we generally  ignore property of number in binary that's why you did't find this till now .

## Concept :

find out number of set odd position  bit from right  (let say it odd_set ) & find number of set even position bit from right (let say is even_set ). set bit means has value 1.

Now if difference of odd_set & even_set divisible by 3 than it is divisible otherwise not divisible by 3 .
& treat 0 & 1 as special case ..

### C++ Code :

1. /*
2.   to check divisibility of a number by 3
3.   ..Most efficent way to check if number is large;
4. */
5. /*
6.   **************************************** CONCEPT **********************************
7.   it is based on concept that
8.   (total set bit at odd position from right - total set bit at even position )
9.   is divisible by 3 than Number is divisible by 3
10.   ************************************************************************************
11. */
12. #include<iostream>
13. #include<math.h>
14. using namespace std;
15. int IsDivBy3(int n)   //function def
16. {
17.         int even=0,odd=0;
18.
19.         /****************special case****************/
20.         if(n==0) return 1;
21.         else if(n==1) return 0;
22.         /******************************************/
23.
24.         if(n<0) n=-n; //to make number positive;
25.
26.         while(n>0)
27.          {
28.                 if(& 1)  //and operation
29.                    odd++;
30.                 n=n>>1; //right sift in binary by 1 ex: 1011 -> 011
31.
32.                 if(& 1) //and operation
33.                    even++;
34.                 n=n>>1;  //right sift in binary by 1 ex: 1011 -> 011
35.          }
36.          if((abs(even-odd))%3==0)
37.             return(1);
38.         else
39.             return(0);
40. }
41. main()
42. {
43.         int n;
44.         cout<<"enter number to check divisibility by 3 : ";
45.         cin>>n;
46.         if(IsDivBy3(n))   //call this function to check it return 1 if divisible otherwise 0
47.            cout<<"divisible";
48.         else
49.            cout<<"Not divisible";
50.
51.         return 0;
52. }

Hope you enjoy this technique ..

Related Post : TOWER OF HANOI