# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

SIMPLE

# PROBLEM:

Determine the number of integers in the range L to R (endpoints inclusive) whose sum of digits is divisible by 3.

# EXPLANATION:

A well known theorem from elementary number theory goes as follows:

A number is divisible by 3 if and only if the sum of its digits is divisible by 3.

Thus, the number of integers in the range [L, R] whose sum of digits is divisible by 3 is equal to the number of integers in the range divisible by 3.

Another well known theorem from elementary number theory says:

The number of integers in the range [1, N] divisible by d is equal to \lfloor\frac N d \rfloor, where \lfloor x \rfloor is the largest integer less than x.

Therefore, the number of integers in the range [L, R] divisible by 3 = number of integers in the range [1,R] divisible by 3 - number of integers in the range [1,L-1] divisible by 3 = \lfloor\frac R 3\rfloor -\lfloor\frac {L-1} 3\rfloor.

# TIME COMPLEXITY:

per test case.

# SOLUTIONS:

Editorialist’s solution can be found here.

**Experimental:** For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters