Codesignal: reciprocal

Original problem

For 1 ÷ n, return the dth digit after the decimal place.

Example

Input/Output

Solution

From the problem definition, we know that we have given a unit fraction \(\frac{1}{n}\) and we want to know digit \(d\) from it's decimal expansion. Writing this fact down gives

\[\frac{1}{n} = '0.xxxdxxx'\]

Which means that our digit at position \(d\) is surrounded by arbitrary digits, we're not interested in. When we multiply both sides by \(10^d\) the following happens:

\[\frac{10^d}{n} = 'xxxd.xxx'\]

In order to get the digit we simply need to cut off the decimal places and extract the last digit of the resulting integer:

\[\text{digit} = \left\lfloor \frac{10^d}{n}\right\rfloor \bmod 10\]

That's pretty much the solution already. But as \(d\) can become quite large, it's impossible to calculate the digit without a decimal number library. But what we can do is dragging in the mod 10:

\[\text{digit} = \left\lfloor \frac{10^d\bmod 10n}{n}\right\rfloor\]

Using modulo exponentiation, which can be calculated logarithmically to the exponent, the solution is already quite fast. We can however, factor out 10 to make it even faster, but it might result in a a few bytes more to the source code:

\[\text{digit} = \left\lfloor 10\frac{10^{d-1}\bmod n}{n}\right\rfloor\]

The solution implemented in Python then looks like the following, ignoring the floor, since codefight accepts it anyway.

reciprocal = lambda n, d: pow(10, d, 10 * n) / n

« Back to problem overview