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

c math

12,070

Solution 1

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

Solution 2

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.

Solution 3

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.

Solution 4

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

Solution 5

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

View more solutions

12,070