Logic to check the number is divisible by 3 or not

Question

without using %, / or * , I have to find the no. is divisible by 3 or not?

it might be an interview question.

Thanks.

Answer 1

Here is a reasonably efficient algorithm for large numbers. (Well not very efficient, but reasonable given the constraints.)

Use sprintf to convert it to a string, convert each digit back to a number. Add up the digits. If you come up with 3, 6, or 9, it is divisible by 3. Anything else less than 10, it is not. Anything over 9, recurse.

For instance to test the number 813478902 you'd stringify, then add the digits to get 42, add those digits to get 6, so it is divisible by 3.

Answer 2

You could use user feedback:

int isDivisibleBy3(int n)
{
   int areDivisibleBy3[] = {};
   for(int i = 0; i < 0; i++)
   {
       if(n == areDivisibleBy3[i])
       {
           return 1;
       }
   }

   return 0;
}

When a user reports a bug stating that a number that is divisble by 3 is not giving the correct result, you simply add that number to the array and increase the number i is compared to in the for loop condition.

This is great because then you never have to worry about numbers the user never uses.

Don't forget to add a unit test for whenever a user reports a bug!

Answer 3

just use a for loop subtracting 3 over and over and see if you get to 0. if you get to negative without getting to 0 then you know its not divisible by 3

Answer 4

Suppose n is the number in question and it is non-negative.

If n is 0 it is divisible by 3; otherwise n = (2^p)*(2*n1+1) and n is divisible by 3 iff 2*n1+1 is, iff there is a k>=0 with 2*n1+1 = 3*(2*k+1) iff n1 = 3*k+1 iff n1=1 or n1> 1 and n1-1 is divisible by 3. So:

int ism3( int n)
{   for(;n;)
    {    while( !(n & 1)) n >>= 1;
         n >>= 1;
         if ( n == 0) return 0;
         n-= 1;
    }
    return 1;
 }

Answer 5

Subtract 3 until you either

hit 0 - number was divisible by 3 (or)

get a number less than 0 - number wasn't divisible

 if (number > 0)
 {
        while (number > 0)
        {
            number -= 3;
    }
}
else if( number < 0)
{
    while number < 0:
        number += 3
}
return number == 0

Answer 6

There are various ways. The simplest is pretty obvious:

int isdivby3(int n) {
    if (n < 0) n = -n;

    while (n > 0) n -= 3;

    return n == 0;
}

But we can improve that. Any number can be represented like this: ("," means range inclusive):

Base2 (AKA binary)
(0,1) + 2*(0,1) + 4*(0,1)

Base4
(0,3) + 4*(0,3) + 16*(0,3)

BaseN
(0,N-1) + N*(0,N-1) + N*N*(0,N-1)

Now the trick is, a number x is divisible by n-1 if and only if the digitsum of x in base n is divisible by n-1. This trick is well-known for 9:

1926 = 6 + 2*10 + 9*100 + 1*1000
6+2+9+1 = 8 + 1*10
8+1 = 9 thus 1926 is divisible by 9

Now we can apply that for 3 too in base4. And were lucky since 4 is a power of 2 we can do binary bitwise operations. I use the notation number(base).

27(10) = 123(4)
Digitsum
12(4)
Digitsum again
3(4) = Divisible!

Now let's translate that to C:

int div3(int n) {
    if (n < 0) n = -n;
    else if (n == 0) return 1;

    while (n > 3) {
        int d = 0;

        while (n > 0) {
            d += n & 3;
            n >>= 2;
        }

        n = d;
    }

    return n == 3;
}

Blazing fast.