166. Fraction to Recurring Decimal

Time: O(n)

Space: O(n)

Intuition

Long division: track remainders in a HashMap. When a remainder repeats, the decimal portion from that point is the repeating part. Insert parentheses at the stored position.

Algorithm

1Handle sign and zero separately. Work with absolute values as long.
2Integer part = numerator / denominator. Remainder = numerator % denominator.
3While remainder != 0: if remainder in map -> insert "(" at map[remainder] and append ")". Break.
4Else store map[remainder] = current position. Multiply remainder by 10. Append (remainder / denominator). remainder %= denominator.
5Return result.

Example Walkthrough

Input: numerator=1, denominator=6

1.Integer part=0. Remainder=1.
2.1->10/6=1, remainder=4. 4->40/6=6, remainder=4.
3.Remainder 4 repeats -> insert "(" at position where 4 first appeared. Append ")". -> "0.1(6)".

Output: "0.1(6)"

Common Pitfalls

•Use long to avoid overflow - INT_MIN / -1 overflows int.
•Handle negative results: exactly one of numerator/denominator is negative.

166.cs

// Approach: Simulate long division; use a HashMap to detect when a remainder
// repeats and mark the cycle start with parentheses.
// Time: O(n) Space: O(n)

public class Solution
{
    public string FractionToDecimal(int numerator, int denominator)
    {
        // Handle zero numerator case
        if (numerator == 0)
            return "0";

        StringBuilder result = new StringBuilder();

        // Determine if result should be negative
        // XOR returns true only when signs are different
        bool isNegative = (numerator > 0) ^ (denominator > 0);
        if (isNegative)
            result.Append("-");

        // Convert to long to avoid integer overflow
        long dividend = Math.Abs((long)numerator);
        long divisor = Math.Abs((long)denominator);

        // Append integer part
        result.Append(dividend / divisor);

        // Calculate remainder
        dividend %= divisor;

        // If remainder is 0, there's no fractional part
        if (dividend == 0)
            return result.ToString();

        // Append decimal point for fractional part
        result.Append(".");

        // Dictionary to store remainder and its corresponding position in result
        // Used to detect repeating patterns
        Dictionary<long, int> remainderToPosition = new Dictionary<long, int>();

        // Process fractional part
        while (dividend != 0)
        {
            // Check if this remainder has appeared before (repeating pattern found)
            if (remainderToPosition.ContainsKey(dividend))
            {
                // Insert opening parenthesis at the start of repeating sequence
                int repeatStartPosition = remainderToPosition[dividend];
                result.Insert(repeatStartPosition, "(");
                // Append closing parenthesis at the end
                result.Append(")");
                break;
            }

            // Store current remainder and its position
            remainderToPosition[dividend] = result.Length;

            // Multiply remainder by 10 for next digit calculation
            dividend *= 10;

            // Append next digit of fractional part
            result.Append(dividend / divisor);

            // Calculate new remainder
            dividend %= divisor;
        }

        return result.ToString();
    }
}

Was this solution helpful?