reference:

Problem Definition:

The very first solution that comes to our mind is the one that we learned in school.If sum of digits in a number is multiple of 3 then number is multiple of 3 e.g., for 612 sum of digits is 9 so it’s a multiple of 3. But this solution is not efficient. You have to get all decimal digits one by one, add them and then check if sum is multiple of 3.

There is a pattern in binary representation of the number that can be used to find if number is a multiple of 3.If difference between count of odd set bits (Bits set at odd positions) and even set bits is multiple of 3 then is the number.

Solution:

1) Make n positive if n is negative.2) If number is 0 then return 13) If number is 1 then return 04) Initialize: odd_count = 0, even_count = 05) Loop while n != 0    a) If rightmost bit is set then increment odd count.    b) Right-shift n by 1 bit    c) If rightmost bit is set then increment even count.    d) Right-shift n by 1 bit6) return isMutlipleOf3(odd_count - even_count)// do this recursively

Code:

/* Fnction to check if n is a multiple of 3*/int isMultipleOf3(int n){    int odd_count = 0;    int even_count = 0;     /* Make no positive if +n is multiple of 3       then is -n. We are doing this to avoid       stack overflow in recursion*/    if(n < 0)   n = -n;    if(n == 0) return 1;    if(n == 1) return 0;     while(n)    {        /* If odd bit is set then           increment odd counter */        if(n & 1)            odd_count++;        n = n>>1;         /* If even bit is set then           increment even counter */        if(n & 1)            even_count++;        n = n>>1;    }      return isMultipleOf3(abs(odd_count - even_count));}

转载地址：http://dexti.baihongyu.com/

你可能感兴趣的文章

链睿和家乐福合作推出下一代零售业隐私保护技术