Check if a number is divisible by 3

Question

Not sure if it's a duplicate. But I need to find whether a number is divisible by 3 without using %, / or *. The hint given was to use atoi() function. Any idea how to do it?

Answer 1

Split the number into digits. Add the digits together. Repeat until you have only one digit left. If that digit is 3, 6, or 9, the number is divisible by 3. (And don't forget to handle 0 as a special case).

Answer 2

A number is divisible by 3 if all the digits in the number when added gives a result 3, 6 or 9. For example 3693 is divisible by 3 as 3+6+9+3 = 21 and 2+1=3 and 3 is divisible by 3.

Answer 3

A number divisible by 3, iirc has a characteristic that the sum of its digit is divisible by 3. For example,

12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9

Answer 4

well a number is divisible by 3 if all the sum of digits of the number are divisible by 3. so you could get each digit as a substring of the input number and then add them up. you then would repeat this process until there is only a single digit result.

if this is 3, 6 or 9 the number is divisable by 3.

Answer 5

Given a number x. Convert x to a string. Parse the string character by character. Convert each parsed character to a number (using atoi()) and add up all these numbers into a new number y. Repeat the process until your final resultant number is one digit long. If that one digit is either 3,6 or 9, the origional number x is divisible by 3.

Answer 6

Subtract 3 until you either

a) hit 0 - number was divisible by 3

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

-- edited version to fix noted problems

if n > 0:
    while n > 0:
        n -= 3
elif n < 0:
    while n < 0:
        n += 3
return n == 0

Answer 7

The current answers all focus on decimal digits, when applying the "add all digits and see if that divides by 3". That trick actually works in hex as well; e.g. 0x12 can be divided by 3 because 0x1 + 0x2 = 0x3. And "converting" to hex is a lot easier than converting to decimal.

Pseudo-code:

int reduce(int i) {
  if (i > 0x10)
    return reduce((i >> 4) + (i & 0x0F)); // Reduces 0x102 to 0x12 to 0x3.
  else
   return i; // Done.
}
bool isDiv3(int i) {
  i = reduce(i);
  return i==0 || i==3 || i==6 || i==9 || i==0xC || i == 0xF;
}

[edit] Inspired by R, a faster version (O log log N):

int reduce(unsigned i) {
  if (i >= 6)
    return reduce((i >> 2) + (i & 0x03));
  else
   return i; // Done.
}
bool isDiv3(unsigned  i) {
  // Do a few big shifts first before recursing.
  i = (i >> 16) + (i & 0xFFFF);
  i = (i >> 8) + (i & 0xFF);
  i = (i >> 4) + (i & 0xF);
  // Because of additive overflow, it's possible that i > 0x10 here. No big deal.
  i = reduce(i);
  return i==0 || i==3;
}

Answer 8

The interview question essentially asks you to come up with (or have already known) the divisibility rule shorthand with 3 as the divisor.

One of the divisibility rule for 3 is as follows:

Take any number and add together each digit in the number. Then take that sum and determine if it is divisible by 3 (repeating the same procedure as necessary). If the final number is divisible by 3, then the original number is divisible by 3.

Example:

16,499,205,854,376
=> 1+6+4+9+9+2+0+5+8+5+4+3+7+6 sums to 69
=> 6 + 9 = 15 => 1 + 5 = 6, which is clearly divisible by 3.

See also

• Wikipedia/Divisibility rule - has many rules for many divisors

Answer 9

While the technique of converting to a string and then adding the decimal digits together is elegant, it either requires division or is inefficient in the conversion-to-a-string step. Is there a way to apply the idea directly to a binary number, without first converting to a string of decimal digits?

It turns out, there is:

Given a binary number, the sum of its odd bits minus the sum of its even bits is divisible by 3 iff the original number was divisible by 3.

As an example: take the number 3726, which is divisible by 3. In binary, this is 111010001110. So we take the odd digits, starting from the right and moving left, which are [1, 1, 0, 1, 1, 1]; the sum of these is 5. The even bits are [0, 1, 0, 0, 0, 1]; the sum of these is 2. 5 - 2 = 3, from which we can conclude that the original number is divisible by 3.

Answer 10

You didn't tag this C, but since you mentioned atoi, I'm going to give a C solution:

int isdiv3(int x)
{
    div_t d = div(x, 3);
    return !d.rem;
}

Answer 11

My solution in Java only works for 32-bit unsigned ints.

static boolean isDivisibleBy3(int n) {
  int x = n;
  x = (x >>> 16) + (x & 0xffff); // max 0x0001fffe
  x = (x >>> 8) + (x & 0x00ff); // max 0x02fd
  x = (x >>> 4) + (x & 0x000f); // max 0x003d (for 0x02ef)
  x = (x >>> 4) + (x & 0x000f); // max 0x0011 (for 0x002f)
  return ((011111111111 >> x) & 1) != 0;
}

It first reduces the number down to a number less than 32. The last step checks for divisibility by shifting the mask the appropriate number of times to the right.