LeetCode Solutions Blog

Equal Rational Numbers

Difficulty: Hard

Problem Description

Given two strings s and t, each of which represents a non-negative rational number, return true if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.

Key Insights

Rational numbers can be expressed in various formats, including integer, decimal with non-repeating parts, and decimal with repeating parts.
Repeating decimals can be converted into fractions to facilitate comparison.
Accurate string parsing is essential to extract integer, non-repeating, and repeating parts from the input strings.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

To determine if two rational numbers represented as strings are equal, we can convert both strings into a common format. The approach involves the following steps:

Parse each string to separate the integer part, non-repeating part, and repeating part.
Convert the non-repeating and repeating parts into a numerical representation.
Use a common denominator to compare both rational numbers effectively.
Return true if the two representations are equal; otherwise, return false.

This algorithm primarily utilizes string manipulation and arithmetic operations to achieve the desired result.

Code Solutions

def equalRationalNumbers(s: str, t: str) -> bool:
    def parse_number(num: str) -> float:
        if '(' in num:
            main_part, repeat_part = num.split('(')
            repeat_part = repeat_part[:-1]  # remove the closing parenthesis
        else:
            main_part, repeat_part = num, ''
        
        if '.' in main_part:
            integer_part, non_repeating = main_part.split('.')
        else:
            integer_part, non_repeating = main_part, ''
        
        # Convert integer part to float
        integer_value = int(integer_part) if integer_part else 0
        
        # Calculate the value of the non-repeating and repeating parts
        non_repeating_value = float('0.' + non_repeating) if non_repeating else 0
        
        # If there's a repeating part, we need to account for it
        if repeat_part:
            repeat_length = len(repeat_part)
            # Calculate the value contributed by the repeating part
            complete_value = non_repeating + repeat_part
            repeating_value = float(complete_value) * (10**repeat_length) / (10**repeat_length - 1) - non_repeating_value
        else:
            repeating_value = 0
        
        total_value = integer_value + non_repeating_value + repeating_value
        return total_value

    return parse_number(s) == parse_number(t)