Solution: Fraction to Recurring Decimal

Statement

Given the two integer values of a fraction, numerator and denominator, implement a function that returns the fraction in string format. If the fractional part repeats, enclose the repeating part in parentheses.

Constraints:

• denominator $!= 0$
• $-2^{31} \leq$ numerator, denominator $\leq 2^{31} - 1$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach is to use an array to store the remainders to determine the repetition of remainders. We can detect repetitions by checking if the remainder already exists in the array during each calculation. This approach involves using a nested loop, with the outer loop calculating the remainder and the inner loop searching for the remainder in the array.

The time complexity of this approach is $O(|d|^2)$, where $d$ is the number of digits in the denominator. This is because we’re using a nested loop. Let’s see if we can use the hash map pattern to find a faster solution.

Optimized approach using hash maps

To solve this problem, we can use the hash map pattern to develop a faster solution. The idea is to use a hashmap to store the remainder, and every time we calculate the remainder, we can check if the remainder is already in the hash map in $O(1)$ time complexity.