Codesignal Solution: reciprocal

Original problem

For 1 ÷ n, return the d^th digit after the decimal place.

Example

• For n = 7 and d = 1, the output should be
  reciprocal(n, d) = 1

  The first few digits of 1 ÷ 7 are 0.142.... 1 is the first digit after the decimal place.

• For n = 8 and d = 8, the output should be
  reciprocal(n, d) = 0

  The first eight digits after the decimal place of 1 ÷ 8 are 0.12500000.

Input/Output

• [time limit] 4000ms (php)

• [input] integer n

  The reciprocal from which to return a digit.

  Guaranteed constraints:
  1 ≤ n ≤ 10⁵

• [input] integer d

  The number of the digit after the decimal place to return.

  Guaranteed constraints:
  1 ≤ d ≤ 10⁹

• [output] integer

  The d^th digit after the decimal place of 1 ÷ n (the reciprocal of n).

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