algoadvance

Given two integers representing the numerator and 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)”

Clarifying Questions

  1. Can the numerator be negative?
    • Yes, the numerator can be negative.
  2. Can the denominator be negative?
    • Yes, the denominator can be negative.
  3. What should be returned if the result is a whole number?
    • Return the whole number without a fractional part, e.g., 2 instead of 2.0.
  4. What if the fraction results in a very large repeating sequence?
    • The problem guarantees that the repeating sequence can be denoted within a reasonable limit using parentheses as in the examples provided.

Strategy

  1. Handle Sign: Determine the sign of the result based on the signs of the numerator and the denominator.
  2. Handle Absolute Values: Work with the absolute values of numerator and denominator for simplicity.
  3. Determine Integral Part: Perform integer division to get the integral part of the fraction.
  4. Handle Remainder and Fractional Part:
    • Use the remainder to compute the fractional part.
    • Use a dictionary to keep track of seen remainders and their positions to identify the start of a repeating sequence.
  5. Build Result String: Construct the result string using the integral part and fractional part, adding parentheses around repeating sequences if found.

Code

def fractionToDecimal(numerator: int, denominator: int) -> str:
    if numerator == 0:
        return "0"
    
    result = []
    
    # Determine the sign of the result
    if (numerator < 0) ^ (denominator < 0):
        result.append("-")
    
    # Use absolute values for simplicity
    numerator, denominator = abs(numerator), abs(denominator)
    
    # Integral part
    integral_part = numerator // denominator
    result.append(str(integral_part))
    
    # Remainder part
    remainder = numerator % denominator
    if remainder == 0:
        return "".join(result)  # No fractional part
    
    result.append(".")
    
    # Dictionary to store seen remainders and their positions
    seen_remainders = {}
    fractional_part = []
    
    while remainder != 0:
        if remainder in seen_remainders:
            # Found a repeating remainder
            start = seen_remainders[remainder]
            fractional_part.insert(start, "(")
            fractional_part.append(")")
            break
        
        # Store the position of this remainder
        seen_remainders[remainder] = len(fractional_part)
        
        remainder *= 10
        fractional_part.append(str(remainder // denominator))
        remainder %= denominator
    
    result.extend(fractional_part)
    return "".join(result)

# Example Outputs
print(fractionToDecimal(1, 2))  # Output: "0.5"
print(fractionToDecimal(2, 1))  # Output: "2"
print(fractionToDecimal(2, 3))  # Output: "0.(6)"

Time Complexity

The time complexity of this solution is O(k), where k is the length of the fractional part before a repeat starts. This is because each digit of the fractional part is computed once and stored in the dictionary until a repeat is found or the remainder becomes zero. Thus, the solution is efficient and suitable for the typical constraints encountered in coding interviews.

Try our interview co-pilot at AlgoAdvance.com