LeetCode Solutions Blog

Equal Rational Numbers

Number: 1012

Difficulty: Hard

Paid? No

Companies: Microsoft

Problem Description

Given two strings s and t representing non-negative rational numbers possibly containing repeating decimal parts enclosed in parentheses (e.g., "0.(52)" or "1.(9)"), determine whether they represent the same number. The number strings can be in one of three formats: a simple integer, a decimal with a non-repeating fractional part, or a decimal with both a non-repeating part and a repeating part.

Key Insights

Convert the string representation into a fractional representation (numerator/denominator) to accurately compare numbers.
For a number with a repeating decimal portion, use the formula:
- If A = integer part, B = non-repeating part (with length L), and R = repeating part (with length K), then:
  - value = A + (B/10^L) + (R/(10^L * (10^K - 1))).
Combine parts into one fraction and reduce it using the greatest common divisor (GCD) for proper comparison.
Handling edge cases like missing fractional part or repeating part is crucial.

Space and Time Complexity

Time Complexity: O(n) per string conversion, where n is the length of the string, since we are doing basic arithmetic and string parsing. Space Complexity: O(1) extra space, aside from the output fraction values.

Solution

We parse each input string into its integer part, non-repeating part, and repeating part. If there is no repeating group, the fraction is simply formed using the integer and non-repeating parts. If there is a repeating part, we use the formula to combine:

Numerator = integerPart * (10^L * (10^K - 1)) + nonRepeatingPart * (10^K - 1) + repeatingPart.
Denominator = 10^L * (10^K - 1). We then reduce the fraction by finding the GCD of the numerator and denominator. Finally, if both strings reduce to the same (numerator, denominator) pair, they represent equal rational numbers.

Data structures used:

Strings for splitting and parsing.
Integers for numerator, denominator, and arithmetic operations.
A helper function to compute GCD.

The algorithm leverages mathematical properties of repeating decimals to convert them to a precise fractional representation for exact comparison.

Code Solutions

# Python solution with detailed comments

import math

def convert_to_fraction(s: str):
    # Split into integer and fractional parts
    if '.' in s:
        integer_part, fractional_part = s.split('.', 1)
    else:
        integer_part, fractional_part = s, ""
    
    # Initialize non-repeating and repeating parts
    non_repeat = ""
    repeat = ""
    
    # Check if there is a repeating part in parentheses
    if '(' in fractional_part:
        # find the index of '(' and ')'
        left_paren = fractional_part.index('(')
        right_paren = fractional_part.index(')')
        non_repeat = fractional_part[:left_paren]
        repeat = fractional_part[left_paren+1:right_paren]
    else:
        non_repeat = fractional_part
    
    # Convert integer part to int
    int_part = int(integer_part) if integer_part else 0
    
    if repeat == "":
        # No repeating part: fraction = int_part + non_repeat/10^(len(non_repeat))
        power = 10 ** len(non_repeat)
        frac_numerator = int(non_repeat) if non_repeat else 0
        numerator = int_part * power + frac_numerator
        denominator = power
    else:
        # There is a repeating part
        L = len(non_repeat)
        K = len(repeat)
        non_repeat_val = int(non_repeat) if non_repeat else 0
        repeat_val = int(repeat)
        # Denominator part for repeating is (10^K - 1)
        rep_den = (10 ** K - 1)
        # Full denominator & numerator calculation based on formula:
        denominator = (10 ** L) * rep_den
        numerator = int_part * denominator + non_repeat_val * rep_den + repeat_val

    # Reduce the fraction using gcd
    gcd_val = math.gcd(numerator, denominator)
    return numerator // gcd_val, denominator // gcd_val

def isRationalEqual(s: str, t: str) -> bool:
    num1, den1 = convert_to_fraction(s)
    num2, den2 = convert_to_fraction(t)
    # Equal if fractions are represented identically after reduction
    return num1 == num2 and den1 == den2

# Example test cases
print(isRationalEqual("0.(52)", "0.5(25)"))  # Expected output: True
print(isRationalEqual("0.1666(6)", "0.166(66)"))  # Expected output: True
print(isRationalEqual("0.9(9)", "1."))  # Expected output: True