How to quickly tell if an "unknown" number is divisible by 3?

Question

I'm trying to tackle down a problem where the time limit is very low (1 second) and the number of cases is supposedly high.

You need to tell if a number is divisible by 3, but the problem is that you don't get the direct number, you get a number k, and then need to check if the concatenation of numbers from 1 to k (123...k) is divisible by 3.

Example input:

4  // The number of cases
2
6
15
130000000

Output:

YES  // Because 12 is divisible by 3
YES  // Because 123456 is divisible by 3
YES  // Because 123456789101112131415 is divisible by 3
NO

I've found some topics about quickly checking the divisibility, but what most time takes I think is to build the number. There are cases where the initial number is as high as 130000000 (so the final is 1234...130000000) which I thinks overflows any numeric data type.

So, what am I missing here? Is there any way to know if something is divisible by 3 without concatenating the number? Any ideas?

PD: Someone also posted the triangular numbers formula which also is a correct solution and then deleted the answer, it was:

if ((1 + num) * num / 2) % 3 == 0 ? "YES" : "NO"

Answer 1

1. Every third number is divisible by three.
2. Every number divisible by three has a digit sum divisible by 3.
3. Every third number has a digit sum divisible by 3.
4. In between these, every third number has a digit sum congruent to 1 and then 2 mod 3.

Take a look:

n    digit sum mod 3
0    0
1    1
2    2
3    0
4    1
5    2
6    0
...
10   1
11   2
12   0
...
19   1
20   2
21   0
...

Say we have a string of digits constructed as you describe, and the number we just added was divisible mod 3. When we append the next number's digits, we are appending digits whose sum is congruent to 1 mod 3, and when added to those in our number, we will get a combined digit sum congruent to 1 mod 3, so our answer for the next one will be "no". The next one will add a number with digit sum congruent to 2 mod 3, and this causes the total to become congruent to 0 again, so the answer here is "yes". Finally, adding the next number which must be divisible by 3 keeps the digit sum congruent to 0.

The takeaway?

• if n is congruent to 0 modulo 3, then the answer is "yes"
• if n is congruent to 1 modulo 3, then the answer is "no"
• if n is congruent to 2 modulo 3, then the answer is "yes"

In particular, your example for n=15 is wrong; the digit string obtained represents a number that should be divisible by 3, and indeed it is (try it on a big enough calculator to verify).

All that is left is to find an implementation that is fast enough and handles all the required cases. If n is guaranteed to be under ~2 billion, then you are probably safe with something like

return (n % 3) != 1;

If n can be an arbitrarily large number, never fear; you can check whether the digit sum is congruent to 0 modulo 3 by adding up the digits in linear time. If not, you can add 1 from the number by coding addition like you do it by hand on paper and then check the result of that for divisibility by 3, again in linear time. So something like:

if (digit_sum_mod_3(n) == 0) return true;
else if (digit_sum_mod_3(add_one(n)) == 0) return false;
else return true;

Then you would have something like

digit_sum_mod_3(n[1...m])
    sum = 0
    for k = 1 to m do
        sum = sum + n[k]
        // keep sum from getting too big
        if sum >= 18 then
            sum = sum - 18
    return sum % 3

add_one(n[1...m])
    // work from right to left, assume big-endian
    for k = m to 1 do
        if n[k] < 9 then // don't need to carry
            n[k] = n[k] + 1
            break
        else then // need to carry
            n[k] = 0
    if n[1] = 0 then // carried all the way to the front
        n[1] = 1
        n[m+1] = 0
    return n

Answer 2

It is a known trick in mathematics that a number is divisible by three if the sum of its individual decimal digits is divisible by three.

Example:

2271

2+2+7+1 = 12

12 is divisible by 3, therefore so is 2271

Additionally, the sum of any three consecutive integers must be divisible by three. This is because:

((n)+(n+1)+(n+2))/3 = (3n+3)/3 = n+1 = integer

Therefore:

If k mod 3 == 0, then concatenation of 1 to k is divisible by three.

If k mod 3 == 1, then concatenation of 1 to k is not divisible by three.

If k mod 3 == 2, then it is a bit trickier. In this case, concatenation of 1 to k is divisible by three if the sum of k and the number before k (which evaluates to (k)+(k-1), which is 2k-1) is divisible by three.

Therefore, the final condition is:

(k mod 3 == 0) || ((k mod 3 == 2) && (2k-1 mod 3 == 0))

However, this can be even further simplified.

It turns out that k mod 3 can only equal 2 whenever 2k-1 mod 3 equals 0 and vice versa.

See simple graph below that shows cyclic pattern of this behavior.

Therefore, the formula can be further simplified just to:

(k mod 3 == 0) || (k mod 3 == 2) 

Or, even more simply:

(k mod 3 != 1)

I realize answerer already provided this answer so I don't expect this to be the accepted answer, just giving a more thorough mathematical explanation.