The basic idea involves Stern-Brocot sequences.

The first Stern-Brocot sequence \(S_1\) is defined as \((\frac 01, \frac 11)\), while subsequent Stern-Brocot sequences are generated by inserting the “mediant” between each pair of neighbors, the mediant of two reduced fractions \(\frac ac\) and \(\frac bd\) being defined as \(\frac {a+b} {c+d}\). For example, the first few Stern-Brocot sequences are:

\(S_1 = (\frac 01, \frac 11)\)

\(S_2 = (\frac 01, \frac 12, \frac 11)\)

\(S_3 = (\frac 01, \frac 13, \frac 12, \frac 23, \frac 11)\)

\(S_4 = (\frac 01, \frac 14, \frac 13, \frac 25, \frac 12, \frac 35, \frac 23, \frac 34, \frac 11)\)

The Stern-Brocot sequences have the property that for any two neighboring fractions, there is no fraction in between them with equal or lower denominator. We can thus describe the procedure for getting the answer by the following pseudocode:

• Initialize \(l := \frac 01\) and \(h := \frac 11\).
• Loop:
  • Find the mediant between \(l\) and \(h\), call it \(m\).
  • If the denominator of \(m\) is greater than \(N\), terminate the loop.
  • Otherwise, set \(l := m\) if \(m \le r\), or otherwise set \(h := m\). (\(*\))
• Among \(l\) and \(h\), print the fraction that’s closest to \(r\).

Essentially, we’re iterating down the Stern-Brocot tree while maintaining the invariant that \(l\) and \(h\) represent Stern-Brocot neighbors that surround \(r\). Thus when we find a mediant whose denominator is too large, we can then terminate the loop, as there are no more fractions with better bounds.

However, implementing this algorithm as-is has a problem: note that the denominators of the second and second-last values of each Stern-Brocot sequence only increases by one each time, so in the worst case we might be looking for a fraction like \(\frac 1 N\), which would take \(O(N)\) iterations.

What we could do, is that instead of directly setting \(l := m\) or \(h := m\) in step (\(*\)), we could use binary search to try to simulate many iterations of the algorithm. For example, in the case \(m \le r\), let \(\frac ac = m\) and \(\frac bd = h\). We can simulate \(k\) iterations of setting \(m := \text {mediant}(m, h)\) with \(m := \frac {a + bk} {c + dk}\) . Using binary search, we can choose a value of \(k\) so that \(m\) does not “overshoot” \(r\), nor its denominator exceed \(N\). We then set \(l\) to this new \(m\). The case \(m > r\) is similar.

Is this improved algorithm fast enough? The number of iterations of the new algorithm now corresponds to the number of “turnings” (direction changes, from left to right or vice versa) we needed to make in the Stern-Brocot tree to get to the optimal \(l\) and \(h\). And we can note that the denominators after each turning will increase at least as fast as the Fibonacci sequence. Thus we will have no more than \(O(\log N)\) turnings. Since the iterations now involve binary search, the total time taken is thus \(O(\log ^2 N)\).

Implementation notes

Note that floating points do not have the precision needed to perform the required calculations, so you want to store rationals in the form of integer numerators and denominators, including when reading \(r\) from the input.

Additionally, comparing two fractions are easiest by multiplying a numerator by the denominator of the other fraction, so the numbers involved can easily overflow a 64-bit integer type. If your language supports 128-bit integers, those can be used. (In the worst case, the values \(r - l\) and \(h - r\) will have numerators up to \(10^{10}\) and denominators up to \(10^{28}\). Comparing these will produce integers up to \(10^{38} < 2^{127}\), so these numbers will just about fit into 128-bit signed integers) ED: this is wrong, is there a better proof of the bounds of the comparison coefficients? My solution still passes all tests. In the absence of a better proof (or the presence of a disproof) it’s still possible to divide the denominators of \(r-l\) and \(h-r\) by the denominator of \(r\) before comparison, to avoid possible overflow.

Note that reduction of the fractions using GCD and division is not needed. Generating the mediant between Stern-Brocot neighbors will always produce a reduced fraction, and the rest of the operations needed (subtraction and comparison) do not require reduced fractions.