Codingame Solution: Recurring Decimals

Original Problem

Solution

This problem is similar to the reciprocal cycles problem of Project Euler 26. This time we need to print the number instead of just calculating the length of repeating digits. For the JavaScript library for rational numbers, I implemented exactly this output format for the toString method. If you look at the git history, you'll see quite a few improvements on the algorithm over time. By now, I use the cycleLength method, derived in the Project Euler problem, plus another method to calculate the cycleStart for the general case. Mathematically seen we need to solve the following modular recurrence relation for the parameters \(s\) and \(t\):

\[10^t \equiv 10^{s+t} \pmod{n}\]

Having the two functions to calculate \(s\) and \(t\), we can print the decimal expansion with the correct brackets quite simply. Calling Fraction.js with the given denominator actually solves this problem quickly. However, let's try to figure out an alternative way to do this in a single run, by combining the algorithm of decimal expansion and parameter calculation. The proposed algorithm doesn't have the general performance of Fraction.js and also needs to store all remainders for the break check (also similar to the length check for Problem 26), but it's a bit less verbose compared to the current official Fraction.js implementation:

var n = +readline();
var i = 0, a = [1], off;
var ret = "";
do {
  var t = a[i] * 10;
  ret+= t / n | 0;
  a[++i] = t % n;
} while(a[i] && i == (off = a.indexOf(a[i])));

if (a[i]) {
  print("0." + ret.slice(0, off) + "(" + ret.slice(off) + ")");
} else {
  print("0." + ret);
}