Logic to check the number is divisible by 3 or not?

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

it might be an interview questi开发者_StackOverflowon.

Thanks.

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.

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

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.

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

To print a count sequence which is divisible by 3 without division or modulus operator.

Notice the count sequence:

00: 00(00)
01: 0001
02: 0010
03: 00(11)
04: 0100
05: 0101
06: 01(10)
07: 0111
08: 1000
09: 10(01)
10: 1010
11: 1011
12: 11(00)
13: 1101
14: 1110
15: 11(11)
16: 10000
17: 10001
18: 100(10)
19: 10011
20: 10100
21: 101(01)

Note that the last two bits of those numbers which are divisible by three (shown in brackets) are cycling through {00, 11, 10, 01} . What we need to check is if the last two bits of the count sequence has these bits in a sequence.

First we start matching with mask = 00 and loop while the first number is not encountered with the lower two bits 00. When a match is found we then do (mask + 03) & 0x03 which gets us the next mask in the set. And we continue to match the last two bits of the next count with 11. Which can be done by ((count & 3) == mask)

The code is

#include <stdio.h>

int main (void)
{
  int i=0;
  unsigned int mask = 0x00;

  for (i=0; i<100;i++)
  {
    if ((i&0x03) == mask)
    {
      printf ("\n%d", i);
      mask = (mask + 3) & 0x03;
    }
  }
  printf ("\n");
  return 0;
}

This is not a general one. Best is to use the solution which @nightcracker have suggested

Also if you really want to implement the division operation i without using the divide operations. I would tell you to have a look at the Non-Restoring Division Algorithm, this can be done in program with a lot of bit manipulations with bitwise operators. Here are some links and references for it.

Wikipedia Link

Here is a demo from UMass

Also have a look at Computer Organization by Carl Hamacher, Zvonko Vranesic, Safwat Zaky

number = abs(number)

while (number > 0)
{
   number -= 3;
}

return number == 0

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;
 }

The simplest way to know if a number is divisible by 3 is to sum all its digits and divide the result by 3. If the sum of the digits is divisible by 3, so the number itself is divisible by 3. For instance, 54467565687 is divisible by 3, because 5+4+4+6+7+5+6+5+6+8+7 = 63, and 63 is divisible by 3. So, no matter how big is the number, you can find if it is divisible by 3 just adding all its digits, and subtracting 3 from the value of this sum until you have a result smaller than 3. If this result is 0, the value of the sum is divisible by 3 (and so the original number), otherwise the sum is not divisible by 3 (and the original number is not divisible, either). It's done much more quickly than subtract 3 successively from the original number (of course, specially if it is a large number) and with no divisions. Um abraço a todos.

Artur

A number is divisible by three if its binary alternating digit sum is zero:

bool by3(int n) {
  int s=0;
  for (int q=1; n; s+=q*(n&1), n>>=1, q*=-1);
  return !s;
}

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!