algoadvance

Leetcode 166. Fraction to Recurring Decimal

Problem Statement

Given two integers representing the numerator and the denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses.

Examples:

  1. Input: numerator = 1, denominator = 2
    Output: “0.5”
  2. Input: numerator = 2, denominator = 1
    Output: “2”
  3. Input: numerator = 2, denominator = 3
    Output: “0.(6)”
  4. Input: numerator = 4, denominator = 333
    Output: “0.(012)”

Clarifying Questions

  1. Q: What kind of inputs can I expect for the numerator and denominator?
    A: The numerator and denominator will always be integers, and the denominator will not be zero.

  2. Q: Can the fraction be negative?
    A: Yes, either numerator or denominator or both can be negative.

  3. Q: What should I return if the result is a whole number?
    A: You should return the whole number without any decimal point.

Strategy

  1. Sign Detection: Determine the sign of the result based on the signs of the numerator and the denominator.
  2. Integer Part: Compute the integer part of the fraction using integer division.
  3. Fractional Part: Use modulus to find the initial remainder and then iterate to find repeating patterns.
  4. Use of Map: Utilize a hash map to keep track of seen remainders and their corresponding positions in the decimal part.
  5. Handling Repeat: If a remainder repeats, then the fraction is repeating from the first occurrence of the remainder.

Code

Here’s a C++ implementation of the strategy:

#include <iostream>
#include <string>
#include <unordered_map>
#include <cmath>

using namespace std;

string fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) return "0";

    string result;

    // Handle negative numbers
    if ((numerator < 0) ^ (denominator < 0)) result += "-";

    // Convert to long to prevent overflow
    long long n = abs((long long)numerator);
    long long d = abs((long long)denominator);

    // Adding the integer part
    result += to_string(n / d);

    long long remainder = n % d;
    if (remainder == 0) return result;

    result += ".";

    unordered_map<long long, int> remainderPositions;
    while (remainder != 0) {
        if (remainderPositions.find(remainder) != remainderPositions.end()) {
            result.insert(remainderPositions[remainder], "(");
            result += ")";
            break;
        }
        
        remainderPositions[remainder] = result.size();
        remainder *= 10;
        result += to_string(remainder / d);
        remainder %= d;
    }

    return result;
}

int main() {
    // Example test cases
    cout << fractionToDecimal(1, 2) << endl; // Output: "0.5"
    cout << fractionToDecimal(2, 1) << endl; // Output: "2"
    cout << fractionToDecimal(2, 3) << endl; // Output: "0.(6)"
    cout << fractionToDecimal(4, 333) << endl; // Output: "0.(012)"
    return 0;
}

Time Complexity

The overall time complexity is O(d), where d is the value of the denominator.

This approach ensures that we handle all required edge cases, including negative numbers, whole numbers, and both terminating and repeating decimals.

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