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.
