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

YOu can develop your algorithm and make it public .. contact us query.b2cs@gmail.com
and you can post your content & algorithm on this blog ..

No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets