How do you solve Equal Rational Numbers on LeetCode?

Equal Rational Numbers (LeetCode #972) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding how to parse and normalize rational numbers is crucial.

What is the brute force solution for Equal Rational Numbers?

The brute force approach for Equal Rational Numbers is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves converting both rational numbers into their decimal representations and comparing them. This is straightforward but inefficient, especially for long repeating decimals. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Equal Rational Numbers?

Equal Rational Numbers uses the following concepts: Math, String. The recommended patterns to study are: String Manipulation, Regular Expressions.

What are the interview tips for Equal Rational Numbers?

Always clarify the input format and constraints with the interviewer. Discuss your thought process and approach before jumping into coding. Test your solution with various examples, including edge cases.

What are common mistakes when solving Equal Rational Numbers?

Failing to handle edge cases like empty repeating parts. Not considering the precision needed for comparison.

#972

Equal Rational Numbers

Hard

MathStringString ManipulationRegular Expressions

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution involves normalizing both rational numbers into a common format and then comparing them directly. This avoids unnecessary decimal generation and handles repeating parts more efficiently.

⚙️

Algorithm

3 steps

1Step 1: Parse both strings to extract integer, non-repeating, and repeating parts.
2Step 2: Normalize the non-repeating and repeating parts to a common decimal representation.
3Step 3: Compare the normalized numbers as strings.

solution.py24 lines

1# Full working Python code
2import re
3
4def normalize_number(num):
5    match = re.match(r'^(\d+)(\.\d+)?\((\d+)\)?$', num)
6    integer_part = match.group(1)
7    non_repeating_part = match.group(2)[1:] if match.group(2) else ''
8    repeating_part = match.group(4) if match.group(4) else ''
9
10    # Normalize the number
11    if repeating_part:
12        non_repeating_length = len(non_repeating_part)
13        repeating_length = len(repeating_part)
14        decimal_length = non_repeating_length + 20  # Simulate precision
15        full_decimal = integer_part + non_repeating_part + repeating_part * (decimal_length // repeating_length + 1)
16        return full_decimal[:len(integer_part) + decimal_length]
17    return integer_part + non_repeating_part
18
19
20def is_equal(s, t):
21    return normalize_number(s) == normalize_number(t)
22
23# Example usage
24print(is_equal('0.(52)', '0.5(25)'))  # Output: True

ℹ

Complexity note: The time complexity is O(n) because we only parse the strings and normalize them without generating large decimal representations. The space complexity is O(n) due to the storage of the normalized strings.

1Understanding how to parse and normalize rational numbers is crucial.
2Recognizing the impact of repeating decimals on comparisons is key.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.