### PROBLEM LINK:

**Author:** Sidhant Bansal

**Testers:** Hasan Jaddouh

**Editorialist:** Sidhant Bansal

### DIFFICULTY:

easy

### PREREQUISITES:

modulo cycle, basic math

### PROBLEM:

The key idea behind the solution is the fact that the digits start to repeat after some time in a cycle of length 4.

Firstly, we will find the sum of all the digits and then check if it is divisible by 3 or NOT.

**Sum of digits** -

We know d_{0} and d_{1}. So what will be d_{2}, d_{3}, ... ?

d_{2} = (d_{0} + d_{1})\mod 10

d_{3} = (d_{2} + d_{1} + d_{0}) \mod 10 = ((d_{0} + d_{1}) \mod 10 + d_{0} + d_{1}) \mod 10 = 2 * (d_{0} + d_{1}) \mod 10

d_{4} = (d_{3} + d_{2} + d_{1} + d{0}) \mod 10 = 4 * (d_{0} + d_{1}) \mod 10

d_{5} = (d_{4} + d_{3} + d_{2} + d_{1} + d_{0}) \mod 10 = 8 * (d_{0} + d_{1}) \mod 10

d_{6} = (d_{5} + ... + d_{1} + d_{0}) \mod 10 = 16 * (d_{0} + d_{1}) \mod 10 = 6 * (d_{0} + d_{1}) \mod 10

d_{7} = (d_{6} + ... + d_{1} + d_{0}) \mod10 = 12 * (d_{0} + d_{1}) \mod 10 = 2 * (d_{0} + d_{1}) \mod 10

If we keep on making d_{i} we will see that the resultant is just looping through the same values.

Rigorously, we can see that d_{0} contributes 1 time(s) to d_{2}, 2 times to d_{3}, 4 times to d_{4}, 8 times to d_{5}, …, 2^{k - 2} times to d_{k}. But since the powers of 2 under modulo 10 cycle from 1, 2, 4, 8, 6, 2, 4, …

Similarly for d_{1}.

Here the cycle length is of 4, where d_{2} is not present in the cycle.

Let S = (2*(d_{0} + d_{1})) \mod 10 + (4*(d_{0} + d_{1})) \mod 10 + (8*(d_{0} + d_{1})) \mod 10 + (6*(d_{0} + d_{1})) \mod 10

So the sum of digits = d_{0} + d_{1} + d_{2} + S * ((k - 3) / 4) + x, here the first 3 terms will be covered by d_{0}, d_{1}, d_{2} and after that the groups of 4 will be covered by S, but this formula will still have not have summed some terms at the end left when (k - 3) is not divisible by 4 (the sum of these terms is denoted by x and the explanation regarding them is given using the example shown below)

Example \rightarrow k = 13, The sum of digits = $d_{0} + d_{1} + d_{2} + S * 2 + x$Then it will have d_{0}, d_{1}, d_{2} then the first S will have d_{3}, d_{4}, d_{5}, d_{6} and the second S will have d_{7}, d_{8}, d_{9}, d_{10}. Now the remaining terms, i.e d_{11} and d_{12} still needs to be added which is being referred to as x in the above formula. For this we can simply say that

d_{11} = 2*(d_{0} + d_{1}) \mod 10

d_{12} = 4*(d_{0} + d_{1}) \mod 10

And x = d_{11} + d_{12}

Time and space complexity of this solution is O(1).

For implementation details please refer to the solutions attached below.