LeetCode 972 - Equal Rational Numbers

Difficulty: 🔴 Hard
Topics: Math, String

Solution

Problem Understanding

The problem asks us to determine whether two strings s and t, each representing a rational number in decimal notation, correspond to the same numerical value. These numbers can be expressed as integers, finite decimals, or decimals with repeating parts denoted by parentheses. For example, 0.1(6) represents 0.1666... repeating indefinitely, while 1. represents the integer 1.

The input strings are constrained such that the integer part has at most 4 digits, the non-repeating decimal part has up to 4 digits, and the repeating part has 1 to 4 digits. The integer part cannot have leading zeros, except for the single digit zero. The task is to return true if the two representations are mathematically equal and false otherwise.

Important edge cases include numbers where the repeating part eventually rounds up to change the integer part, such as 0.9(9) equaling 1., and numbers with varying lengths of repeating cycles like 0.(52) versus 0.5(25).

The challenge is that direct string comparison fails because repeating cycles can be expressed in multiple equivalent ways, so a numeric representation or normalization technique is necessary.

Approaches

A brute-force approach would be to expand the decimal numbers to a very large number of digits and then compare them digit by digit. This would be correct in principle, as eventually two equal rational numbers would match in their decimal expansions. However, it is not practical because repeating cycles can be infinite and cannot be fully enumerated.

The optimal approach is to convert the given number representations into fractions. By treating the integer, non-repeating, and repeating parts separately, we can compute an exact numerator and denominator for each number. Two numbers are equal if and only if their reduced fractions are equal. This approach avoids the pitfalls of infinite decimal expansions and rounding errors.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N) per digit expansion	O(N)	Expand repeating decimals to a fixed large length and compare
Optimal	O(M + R)	O(1)	Convert integer, non-repeating, and repeating parts into exact fractions and compare

Algorithm Walkthrough

Parse the Number Parts: Split each string into integer part, non-repeating decimal part, and repeating decimal part. Use string operations to identify parentheses for repeating segments.
Convert to Fraction: Compute the exact fraction representation. For a number A.B(C):

Let int_part = A.
Let non_repeat = B.
Let repeat = C.
Convert to fraction using the formula:

numerator = int_part * denominator + non_repeat_contrib + repeat_contrib
denominator = 10^(len(B)) * (10^(len(C)) - 1)

This ensures the repeating part is correctly handled. 3. Reduce Fraction: Optionally, reduce the fraction to its lowest terms by dividing numerator and denominator by their greatest common divisor (GCD). This guarantees exact comparison without floating-point errors. 4. Compare Fractions: Two rational numbers are equal if numerator1 * denominator2 == numerator2 * denominator1.

Why it works: By converting each decimal representation to its exact fraction, we avoid the ambiguity of repeating decimals and finite approximations. Rational numbers have a unique representation as irreducible fractions, so equality of fractions guarantees equality of the original numbers.

Python Solution

from math import gcd

class Solution:
    def isRationalEqual(self, s: str, t: str) -> bool:
        def to_fraction(num: str):
            if '.' not in num:
                return int(num), 1
            
            int_part, frac_part = num.split('.')
            if '(' in frac_part:
                non_repeat, repeat = frac_part.split('(')
                repeat = repeat.rstrip(')')
            else:
                non_repeat, repeat = frac_part, ''
            
            int_val = int(int_part) if int_part else 0
            
            if not repeat:
                if not non_repeat:
                    return int_val, 1
                numerator = int(non_repeat)
                denominator = 10 ** len(non_repeat)
            else:
                numerator = int(non_repeat + repeat) - int(non_repeat or '0')
                denominator = (10 ** len(non_repeat + repeat) - 10 ** len(non_repeat))
            
            numerator += int_val * denominator
            g = gcd(numerator, denominator)
            return numerator // g, denominator // g
        
        n1, d1 = to_fraction(s)
        n2, d2 = to_fraction(t)
        return n1 * d2 == n2 * d1

Implementation Explanation: The function to_fraction splits the input into integer, non-repeating, and repeating parts. If there is no repeating part, the fraction is straightforward. For repeating decimals, it calculates the contribution using the formula for geometric series. The fraction is reduced by GCD to ensure exact comparison. Finally, cross multiplication avoids division errors.

Go Solution

package main

import (
	"strconv"
	"strings"
)

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func toFraction(num string) (int, int) {
	parts := strings.Split(num, ".")
	intPart := 0
	if len(parts) > 0 && parts[0] != "" {
		intPart, _ = strconv.Atoi(parts[0])
	}

	if len(parts) == 1 || parts[1] == "" {
		return intPart, 1
	}

	fracPart := parts[1]
	nonRepeat := ""
	repeat := ""
	if strings.Contains(fracPart, "(") {
		subparts := strings.Split(fracPart, "(")
		nonRepeat = subparts[0]
		repeat = strings.TrimRight(subparts[1], ")")
	} else {
		nonRepeat = fracPart
	}

	var numerator, denominator int
	if repeat == "" {
		numerator, _ = strconv.Atoi(nonRepeat)
		denominator = pow10(len(nonRepeat))
	} else {
		full, _ := strconv.Atoi(nonRepeat + repeat)
		base, _ := strconv.Atoi(nonRepeat)
		numerator = full - base
		denominator = pow10(len(nonRepeat+repeat)) - pow10(len(nonRepeat))
	}

	numerator += intPart * denominator
	g := gcd(numerator, denominator)
	return numerator / g, denominator / g
}

func pow10(n int) int {
	res := 1
	for i := 0; i < n; i++ {
		res *= 10
	}
	return res
}

func isRationalEqual(s string, t string) bool {
	n1, d1 := toFraction(s)
	n2, d2 := toFraction(t)
	return n1*d2 == n2*d1
}

Go-specific Notes: Go uses strconv.Atoi to convert strings to integers, and strings.Split to parse the input. The pow10 helper avoids floating-point operations. The logic is almost identical to Python, but integer types and string handling require explicit conversions.

Worked Examples

Example: s = "0.(52)", t = "0.5(25)"

Step	s Fraction Calculation	t Fraction Calculation
Integer Part	0	0
Non-repeating	""	"5"
Repeating	"52"	"25"
Fraction	numerator = 52-0=52, denominator=99 → 52/99	numerator = 525-5=520, denominator=990 → 52/99
Reduced Fraction	52/99	52/99
Comparison	52_99 == 52_99 → true	true

Example: s = "0.9(9)", t = "1."

Step	Fraction Calculation
s: numerator = 9-0=9, denominator = 10-1=9, add int=0 → 9/9 → 1/1
t: numerator=1, denominator=1 → 1/1
Comparison	1_1 == 1_1 → true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(M + R)	Parsing the integer, non-repeating, and repeating parts takes linear time relative to their length
Space	O(1)	Only a fixed number of integer variables are used; no extra arrays proportional to input

The approach is efficient because we do not expand the repeating decimals and instead compute exact fractions directly.

Test Cases

# Basic examples
assert Solution().isRationalEqual("0.(52)", "0.5(25)") == True
assert Solution().isRationalEqual("0.1666(6)", "0.166(66)") == True
assert Solution().isRationalEqual("0.9(9)", "1.") == True

# Non-repeating decimals
assert Solution().isRationalEqual("1.25", "1.2500") == True

# Repeating vs finite
assert Solution().isRationalEqual("0.(3)", "0.3333") == True

# Edge integer
assert Solution().isRationalEqual("1234", "1234.0") == True

# Large repeating pattern
assert Solution().isRationalEqual("0.(1234)", "0.12341234