Trouble understanding a CoC solution: Rotational division numbers

Hi there,

I encountered a Clash of Code a long time ago: Rotational division numbers.

I couldn’t find how to solve it without brute force. This was intended by the creator, Sharky564.

A while ago I remembered it and looked for the contribution. I found the creator solution, but I’m still couldn’t understand why it works (i.e. the math behind it).
I posted a comment asking for help on the puzzle page, but haven’t received a reply.

Can someone explain it to me please? I have some background in maths, even in modular arithmetic.


I have not studied the author’s code in detail, but I guess it is roughly based on this?


k is given as the input.
Let n = [k][n1], where n1 is the rest of the digits, which may or may not start with ‘0’.
Let lk = number of digits in k.
Let ln = number of digits in n1.
Let m = [n1][k]
So given that n / k = m, we may rewrite it as:

       ln                    lk
(k * 10   + n1) / k = n1 * 10   + k

So we need to solve the above equation for n1, by testing the values of ln 1 by 1, until an integer solution of n1 is found.

My draft python solution based on the rationale outlined above works on the small cases, but it fails to pass the bigger cases. Maybe there’s something more to it :stuck_out_tongue:

1 Like

Thanks for replying!

Yes I think there is more to it.

The author’s code generate n in the variable x.
(Beware, the variable names in the author’s code are confusing: n is the input in the code, and k is unrelated to the solution.)

Let lk = number of digits in k.
Let u = 1, left padded with lk-1 zeroes.
Let x = [k][u] (at first)
Let r = 0, a remainder for futures Euclidian divisions (at first)
Let n = [k][n1]

Then the program does an Euclidian division, which is (r * 10^lk + u) / k, (u being all the digits to the right of k in x)
Let q = the quotient of this division
Let r = the remainder of this division

Let lq = number of digits in q
Let p = q, left padded with (lk - lq) zeroes
Let x = [x][p]

If the last lk digits of x evaluate to k, and r is 0, then the program stop, and n is computed as x without the lk rightmost digits. Otherwise, the Euclidian division is performed again.

I understand what the programs does, and I can see that it works, but I don’t understand why it does.