algoadvance

Leetcode 166. Fraction to Recurring Decimal

Problem Statement

You are given two integers representing the numerator and denominator of a fraction. Return the fraction in string format.

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)"

Clarifying Questions

  1. Q: Can the numerator or denominator be zero?
    • A: The denominator will never be zero as per the problem constraints. The numerator can be zero, and in that case, the result should be “0”.
  2. Q: Can the fraction be negative?
    • A: Yes, the fraction can be negative if either numerator or denominator (but not both) is negative.
  3. Q: What should be the output for large numerators and denominators?
    • A: The output should be in string format, and it should handle large values correctly. The problem guarantees the output string length will be less than 10^4.

Code

import java.util.HashMap;
import java.util.Map;

public class FractionToDecimal {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }

        StringBuilder result = new StringBuilder();
        
        // Determine the sign.
        if ((numerator > 0) ^ (denominator > 0)) {
            result.append("-");
        }

        // Convert input values to positives for calculation
        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 decimal point
        result.append(".");

        Map<Long, Integer> map = new HashMap<>();
        while (num != 0) {
            if (map.containsKey(num)) {
                // A repeating fraction found
                result.insert(map.get(num), "(");
                result.append(")");
                break;
            }

            map.put(num, result.length());
            num *= 10;
            result.append(num / den);
            num %= den;
        }

        return result.toString();
    }

    public static void main(String[] args) {
        FractionToDecimal solution = new FractionToDecimal();
        System.out.println(solution.fractionToDecimal(1, 2)); // Output: "0.5"
        System.out.println(solution.fractionToDecimal(2, 1)); // Output: "2"
        System.out.println(solution.fractionToDecimal(2, 3)); // Output: "0.(6)"
    }
}

Strategy

  1. Determine the Sign:
    • Use the XOR operation to determine the sign of the result and handle positive values uniformly.
  2. Integer Part Calculation:
    • Calculate the integer part by performing an integer division of the numerator by the denominator.
  3. Fractional Part Calculation:
    • Use the modulo operator to get the remainder after the integer division.
    • If the remainder is zero, append the integer part to the result and return.
    • Otherwise, use a Map to detect repeating remainders and construct the fractional part.
    • For each remainder, multiply by 10 and continue the division. If a remainder repeats (exists in the map), then the sequence is repeating.
  4. Detect Repetition and Construct the Result:
    • Insert the opening parenthesis at the index where the repeat started and append a closing parenthesis at the current position.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI