Equal Rational Numbers

Hard

Asked by:

4 views

Topics:

Strings

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.

A rational number can be represented using up to three parts: <IntegerPart>, <NonRepeatingPart>, and a <RepeatingPart>. The number will be represented in one of the following three ways:

<IntegerPart>
- For example, 12, 0, and 123.
<IntegerPart><.><NonRepeatingPart>
- For example, 0.5, 1., 2.12, and 123.0001.
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>
- For example, 0.1(6), 1.(9), 123.00(1212).

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets. For example:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Example 1:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Example 2:

Input: s = "0.1666(6)", t = "0.166(66)"
Output: true

Example 3:

Input: s = "0.9(9)", t = "1."
Output: true
Explanation: "0.9(9)" represents 0.999999999... repeated forever, which equals 1.  [See this link for an explanation.]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Constraints:

Each part consists only of digits.
The <IntegerPart> does not have leading zeros (except for the zero itself).
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

Equal Rational Numbers

Hard

Asked by:

4 views

Topics:

Strings

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.

A rational number can be represented using up to three parts: <IntegerPart>, <NonRepeatingPart>, and a <RepeatingPart>. The number will be represented in one of the following three ways:

<IntegerPart>
- For example, 12, 0, and 123.
<IntegerPart><.><NonRepeatingPart>
- For example, 0.5, 1., 2.12, and 123.0001.
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>
- For example, 0.1(6), 1.(9), 123.00(1212).

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets. For example:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Example 1:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Example 2:

Input: s = "0.1666(6)", t = "0.166(66)"
Output: true

Example 3:

Input: s = "0.9(9)", t = "1."
Output: true
Explanation: "0.9(9)" represents 0.999999999... repeated forever, which equals 1.  [See this link for an explanation.]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Constraints:

Each part consists only of digits.
The <IntegerPart> does not have leading zeros (except for the zero itself).
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you please provide the data type for the numerators and denominators (e.g., are they integers, longs, or something else)? What are the possible value ranges for the numerators and denominators?
How should I handle cases where a denominator is zero? Is it considered an invalid input, or should I assume it is handled upstream?
Are the fractions always provided in their simplest form (i.e., are the numerator and denominator coprime)? If not, should I reduce them to their simplest form before comparing them?
Is there a specific tolerance I should use when comparing the floating-point representations of the rational numbers to account for potential precision errors?
For the input strings, can you guarantee a specific format or structure? Should I expect any leading/trailing spaces or invalid characters?

Brute Force Solution

Approach

The brute force approach to comparing rational numbers involves converting both numbers to their decimal representations. Then, to determine if they are equal, we can compare the decimal representations up to a certain precision. The key is to convert the repeating decimals into a manageable representation to compare.

Here's how the algorithm would work step-by-step:

First, convert both given rational numbers (which may include repeating parts) into regular decimal numbers.
For repeating decimals, figure out the repeating pattern and simulate the decimal expansion to a sufficient number of places to get a good approximation.
Once both numbers are represented as regular decimals, compare them digit by digit up to the simulated precision.
If all the digits match up to that precision, we can conclude that the two rational numbers are likely equal. If they differ at any point within the specified precision, they are not equal.

Code Implementation

def are_rational_numbers_equal(rational_number_one, rational_number_two): 
    decimal_one = rational_to_decimal(rational_number_one)
    decimal_two = rational_to_decimal(rational_number_two)
    
    precision = 10
    
    for i in range(precision):
        if abs(decimal_one - decimal_two) < 10**(-precision): 
            return True
        else:
            return False

def rational_to_decimal(rational_number): 
    parts = rational_number.split('(')
    non_repeating_part = parts[0]
    repeating_part = ''

    if len(parts) > 1:
        repeating_part = parts[1][:-1]

    integer_part, fractional_part = non_repeating_part.split('.') if '.' in non_repeating_part else (non_repeating_part, '')

    decimal_value = float(integer_part + '.' + fractional_part) if fractional_part else float(integer_part)

    # Simulate the repeating decimal expansion
    for i in range(10): 
        decimal_value += float(repeating_part) / (10**(len(fractional_part) + len(repeating_part) * (i + 1)))
    
    return decimal_value

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(P) – The runtime is primarily determined by the precision (P) to which we expand the repeating decimals. Converting the rational numbers to decimal representation and simulating the repeating part takes time proportional to P. Comparing the two decimal representations also requires traversing P digits. Thus, the dominant factor is the number of digits we simulate and compare, leading to a time complexity of O(P).

Space Complexity

O(P) – The dominant space complexity stems from storing the decimal representations of the two rational numbers, where 'P' represents the chosen precision for the decimal expansion. We need to store up to 'P' digits for each number, leading to a space requirement proportional to P. Other variables used for calculations have constant space, and are dominated by the space used to store the decimal representation.

Optimal Solution

Approach

The goal is to determine if two rational numbers represented as strings are equal. The clever way to do this involves converting the strings to a standard form by handling repeating decimals and then comparing them directly.

Here's how the algorithm would work step-by-step:

First, separate the whole number part, the non-repeating part, and the repeating part from each rational number string.
If there's a repeating part, convert both rational numbers into a simple fraction format (numerator/denominator). To do this, we'll need to deal with the repeating decimal portion appropriately by shifting decimal places and subtracting to eliminate the repeating part.
Next, simplify both fractions to their lowest terms by finding the greatest common divisor of the numerator and denominator and dividing both by it.
Finally, compare the two simplified fractions. If the numerators and denominators are equal, then the original rational numbers are equal.

Code Implementation

def equal_rational_numbers(rational_1: str, rational_2: str) -> bool:

    def string_to_fraction(rational: str) -> tuple[int, int]:
        if '.' not in rational:
            return int(rational), 1

        whole_number_part = 0
        non_repeating_part = ""
        repeating_part = ""

        if '(' in rational:
            whole_number_part, decimal_part = rational.split('.')
            non_repeating_part, repeating_part = decimal_part.split('(')
            repeating_part = repeating_part[:-1]
        else:
            whole_number_part, non_repeating_part = rational.split('.')

        whole_number = int(whole_number_part)
        non_repeating = int(non_repeating_part) if non_repeating_part else 0
        repeating = int(repeating_part) if repeating_part else 0

        len_non_repeating = len(non_repeating_part)
        len_repeating = len(repeating_part)

        numerator = whole_number
        denominator = 1

        if non_repeating_part:
            numerator = numerator * (10 ** len_non_repeating) + non_repeating
            denominator = 10 ** len_non_repeating

        # Handling the repeating part
        if repeating_part:
            numerator = numerator * (10 ** len_repeating) + repeating
            denominator = denominator * (10 ** len_repeating)

            numerator -= whole_number * (10 ** len_non_repeating) + non_repeating
            denominator -= (10 ** len_non_repeating)

        return numerator, denominator

    def greatest_common_divisor(first_number: int, second_number: int) -> int:
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    def simplify_fraction(numerator: int, denominator: int) -> tuple[int, int]:
        # Simplifies to lowest terms
        common_divisor = greatest_common_divisor(numerator, denominator)
        return numerator // common_divisor, denominator // common_divisor

    numerator_1, denominator_1 = string_to_fraction(rational_1)
    numerator_2, denominator_2 = string_to_fraction(rational_2)

    simplified_numerator_1, simplified_denominator_1 = simplify_fraction(numerator_1, denominator_1)
    simplified_numerator_2, simplified_denominator_2 = simplify_fraction(numerator_2, denominator_2)

    # Compare simplified fractions
    return simplified_numerator_1 == simplified_numerator_2 and simplified_denominator_1 == simplified_denominator_2

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n + k) – The dominant time complexity comes from parsing the input strings of length n and converting repeating decimals to fractions, which involves string manipulation and arithmetic operations proportional to the length of the repeating part (k). Finding the greatest common divisor (GCD) for simplification is generally logarithmic in the size of the numbers involved, but can be considered constant in the context of interview problems with reasonable input sizes, or bounded by the length of the input string. Comparing the resulting numerators and denominators is constant time. Therefore, the overall time complexity is determined by parsing the input and the length of the repeating decimal part, resulting in O(n + k), where k <= n, therefore it is safe to just say O(n).

Space Complexity

O(1) – The algorithm requires a few variables to store the whole number, non-repeating, and repeating parts of the input strings, as well as intermediate results during fraction conversion and simplification. The space used by these variables remains constant regardless of the length of the input strings. The greatest common divisor (GCD) calculation, which is part of simplifying the fraction, also operates in constant space. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Input strings are null or empty	Return true if both are null/empty or false if one is and the other isn't.
Integer overflow during greatest common divisor (GCD) calculation	Use a data type with a larger range or modular arithmetic if appropriate, such as long, to prevent overflow during GCD calculations.
Input strings contain non-numeric characters or invalid formatting	Validate the inputs to ensure that the strings only contain numeric characters, a forward slash, and optionally a repeating decimal section enclosed in parentheses.
Repeating decimal part contains leading zeros	Remove any leading zeros in the repeating section before processing it to avoid misinterpreting the number.
Repeating decimal part is all nines (e.g., 0.(9))	Recognize and simplify such numbers to their equivalent non-repeating forms (e.g., 0.(9) == 1).
Very long repeating decimal parts (performance)	Limit the maximum length of the repeating part to prevent excessive computation and potential denial-of-service attacks.
Negative rational numbers	Handle the negative signs correctly and consistently throughout the comparison process.
Divide by zero	Check for zero denominators and return false if encountered.