Given two integers representing the numerator numerator and denominator denominator of a fraction, return its decimal representation as a string.

If the fractional part is repeating, enclose the repeating portion in parentheses.

If there are multiple possible answers, return any one of them.

For every given input, the answer string is guaranteed to have a length less than 104.

Example 1:

Input:numerator = 1, denominator = 2
Output:"0.5"

Example 2:

Input:numerator = 2, denominator = 1
Output:"2"

Example 3:

Input:numerator = 2, denominator = 3
Output:"0.(6)"

Example 4:

Input:numerator = 4, denominator = 333
Output:"0.(012)"

Example 5:

Input:numerator = 1, denominator = 5
Output:"0.2"

Constraints:

• -231 <= numerator, denominator <= 231 - 1
• denominator != 0

Analysis

#

The core of this problem is to solve it using the reasoning behind long division. How can we detect a repeating decimal while performing division?

First, preprocess the input with the following steps:

1. Normalize the sign. Dividing two positive numbers is clearly easier to reason about.
2. Convert all 32-bit input values to 64-bit values because they may overflow.
3. Process the integer part, which generally does not belong to the repeating fractional portion.
4. Handle the other special cases.

After these steps, we still have the two values from the problem, numerator and denominator. They are still the dividend and divisor, but after removing the integer part, we can guarantee that numerator is smaller than denominator.

If you are stuck, take a look at the image above. It essentially summarizes the mathematical ideas about recurring decimals needed for this problem. During division, when a number does not divide evenly, we use the remainder and continue by multiplying the remainder by 10 before dividing again. Once a remainder repeats, everything that follows is identical as well; in other words, the first occurrence of the repeated remainder marks the beginning of the recurring cycle.

Here we use a hash map to store every remainder seen so far. When a remainder appears for the second time, mark the position where the cycle begins and terminate the program.

Rust Code

#

# struct Solution;
use std::collections::HashMap;
impl Solution {
    pub fn fraction_to_decimal(numerator: i32, denominator: i32) -> String {
        let mut ret = String::new();
        if (numerator as i64 * denominator as i64) < 0 {
            ret.push('-');
        }
        let mut denominator = (denominator as i64).abs();
        let mut numerator = (numerator as i64).abs();
        let pre = numerator / denominator;
        numerator %= denominator;
        let mut map: HashMap<i64, i32> = HashMap::new();
        ret.push_str(&pre.to_string());
        if numerator == 0 {
            return ret;
        }
        ret.push('.');
        let mut ws = ret.len() as i32;
        loop {
            if numerator == 0 {
                break;
            }
            if map.contains_key(&numerator) {
                ret.insert(*map.get(&numerator).unwrap() as usize, '(');
                ret.push(')');
                break;
            }
            map.insert(numerator, ws);
            numerator *= 10;
            ret.push((('0' as u8) + (numerator / denominator) as u8) as char);
            numerator %= denominator;
            ws += 1;
        }
        ret
    }
}