How to solve GeeksForGeeks Divisible by 3 without running the program Can someone please explain to me how to calculate the value of "d" without running the program? This is taken from GeeksForGeeks website.
int d=0;
for(int i=0;i<31;i++)
    for(int j=0;j<31;j++)
        for(int k=0;k<31;k++) {
          if (((i+j+k) % 3)==0) {
              d=d+1;
          }
        }
    }
}

This is a solution someone posted for the problem but, I do not understand how they got this. :(
Set 1 = { 3x | x in (1,10) }
Set 2 = { 3x + 1 | x in (0,10) }
Set 3 = { 3x + 2 | x in (0,9) }
Set containing all numbers from set 1 = 10*10*10 = 1000
Set containing 1 number each from set 1, set 2 and set 3 = 10*11*10*3! = 6600
Set containing numbers from set 2 only = 11*11*11 = 1331
Set containing numbers from set 3 only = 10*10*10 = 1000
Net = 9331
 A: Think about if the program was this instead:
int[3][3][3] count;
// initialize count to zero
memset(count, 0, sizeof(count));

for(int i=0;i<31;i++)
for(int j=0;j<31;j++)
for(int k=0;k<31;k++) {
  count[i%3][j%3][k%3] += 1;
}

Now, what is the value of $\text{count}[x][y][z]$ ?  For example, $\text{count}[0][1][2] = 1100$ tells us that $i \equiv 0 \pmod 3$ and $j \equiv 1 \pmod 3$ and $k \equiv 2 \pmod 3$ exactly $1100$ times.  The value of $\text{count}[x][y][z]$ can be calculated easily without running the program.  


*

*There are $11$ values that are divisible by $3$ in $[0 \dots 30]$: $\quad$ $0, 3, 6, \dots 30$

*There are $10$ values that are 1 more than a multiple of $3$: $\quad$ $1, 4, 7, \dots 28$

*There are $10$ values that are 2 more than a multiple of $3$: $\quad$ $2, 5, 8, \dots 29$


So $\text{count}[0][0][0]$ is just $11 \times 11 \times 11$, and $\text{count}[1][0][2]$ is just $10 \times 11 \times 10$, etc.
So if you want to count the number of times $i + j + k \equiv 0 \pmod 3$, it is just the number of times $\text{count}[x][y][z]$ is incremented when $x + y + z \equiv 0 \pmod 3$.  That occurs when 


*

*$x = y = z = 0$, or $\text{count}[0][0][0]$ times, or $11^3$ times

*$x = y = z = 1$, or $\text{count}[1][1][1]$ times, or $10^3$ times

*$x = y = z = 2$, or $\text{count}[2][2][2]$ times, or $10^3$ times

*$x = 0, y = 1, z = 2$, or one of the $3!$ ways $x, y, z$ can be assigned the values $0, 1, 2$, so $3! \times 11 \times 10 \times 10$.


So altogether it is $11^3 + 10^3 + 10^3 + 3!\times 11 \times 10 \times 10 = 9931$.
A: A faster way to count is to divide the solutions into three classes:


*

*$k\ne 0$. For each combination of $i$ and $j$ there is exactly $10$ values of $k$ between $1$ and $30$ that makes the sum a multiple of $3$. This gives $31\cdot 31\cdot 10$ combinations.

*$k=0, j\ne 0$. For each $i$ there is exactly $10$ values of $j$ between $1$ and $30$ that makes the sum a multiple of $3$. This gives $31\cdot 10$ combinations.

*$k=0, j=0$. There are $11$ values of $i$ that are multiples of $3$.


So,
$$ 31\cdot31\cdot10 + 31\cdot10 + 11 = 9931 $$
