Fraction to Recurring Decimal in Java

We must return a fraction in string format given two numbers that represent the fraction's numerator and denominator. If there is a recurring portion in the factorial, we put it in parentheses.

Example 1:

Input:

Numerator: 3

Denominator: 4

Output: "0.75"

Explanation: Here the when we divide the numerator with denominator we get a perfect decimal. So we return the ouput "0.75"

Input:

Numerator: 2

Denominator: 3

Output: " 0.(6)"

Explanation: Here the when we divide the numerator with denominator we do not get a perfect decimal. So we keep the recurring number in parentheses and return the value as " 0.(6)".

Long Division Approach

In this approach, the decimal component is appended, the fractional part is handled by computing remainders and attaching digits, and recurrent patterns in the fractional part are identified through the use of a hash map.

FileName: FractionToRecurringDecimal.java

import java.util.HashMap;

import java.util.Map;

public class FractionToRecurringDecimal {

    public static String fractionToDecimal(int numerator, int denominator) {

        if (numerator == 0) return "0"; // If numerator is zero, return "0"

        StringBuilder result = new StringBuilder();

        // Handle the sign

        result.append((numerator > 0) ^ (denominator > 0) ? "-" : "");

        long num = Math.abs((long) numerator);

        long den = Math.abs((long) denominator);

        // Append the integer part

        result.append(num / den);

        num %= den;

        if (num == 0) return result.toString();

        // Append the fractional part

        result.append(".");

        Map map = new HashMap<>();

        map.put(num, result.length());

        while (num != 0) {

            num *= 10;

            result.append(num / den);

            num %= den;

            if (map.containsKey(num)) {

                int index = map.get(num);

                result.insert(index, "(");

                result.append(")");

                break;

            } else {

                map.put(num, result.length());

            }

        }

        return result.toString();

    }

    public static void main(String[] args) {

        int numerator = 2;

        int denominator = 3;

        System.out.println(fractionToDecimal(numerator, denominator));

        int numerator1 = 2;

        int denominator1 = 4;

        System.out.println(fractionToDecimal(numerator1, denominator1));

    }

}

Output:

0.(6)

0.5

Complexity Analysis:

Time Complexity: O(n), where n is the number of digits in the resulting decimal.

Space Complexity: O(n+den),  where n is the number of digits in the resulting decimal and den is the denominator of the fraction.