Equal Rational Numbers

Problem Statement

Given two strings s and t, both representing non-negative rational numbers, the objective is to determine if they signify the same numeric value. These strings are composed of distinct sections that define a rational number, potentially including a repeating sequence denoted by parentheses. Rational numbers are defined as follows:

• A purely integer form, for instance, 12 or 0.
• An integer followed by a non-repeating decimal, such as 1.23.
• An integer with a non-repeating decimal and a repeating part enclosed in parentheses, like 0.1(6).

The challenge lies in correctly interpreting these textual representations and checking if both strings, despite potential differences in their format (like differing repetitions or placements of decimal points), ultimately represent the identical value.

Examples

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

Approach and Intuition

The primary task is to accurately evaluate and compare the numbers denoted by the strings s and t. Each example and constraint helps in understanding how to handle different formats of rational numbers. Here's a strategy based on the examples provided:

1. Normalization: Convert both strings into a common format that can be easily compared. This involves expanding the repeating sequences into an infinite decimal format or using a mathematical representation that encapsulates the repeating nature without literal infinity.

2. Comparative Analysis:

   • For strings like "0.(52)" and "0.5(25)", despite the different placements of parentheses, both represent the same sequence of infinite decimals. Thus, normalizing to a common format like 0.525252... confirms their equality.
   • When encountering formats like "0.9(9)" versus "1.", recognize the mathematical idea that 0.9999... equals 1, thus affirming both represent the same number.

3. Handling Edge Cases:

   • Ensure that numbers like 0.123000(1234) are seen as different from 0.123(12340000) due to the infinite extension and decimal place values differing substantially post normalization.

This problem requires careful string manipulation and a solid understanding of how repeating decimals work mathematically and how they can be translated into a repetitively comparable format.

Solutions

class RationalComparator {
    public boolean compareRationalStrings(String first, String second) {
        RationalFraction frac1 = parseFraction(first);
        RationalFraction frac2 = parseFraction(second);
        return frac1.num == frac2.num && frac1.den == frac2.den;
    }

    public RationalFraction parseFraction(String strFraction) {
        int stage = 0; // Parsing stages: whole, fractional, repeating
        RationalFraction result = new RationalFraction(0, 1);
        int fracLength = 0;

        for (String part: strFraction.split("[.()]")) {
            stage++;
            if (part.isEmpty()) continue;
            long partValue = Long.parseLong(part);
            int length = part.length();

            if (stage == 1) { // Whole number part
                result.increment(new RationalFraction(partValue, 1));
            } else if (stage == 2) { // Fractional part
                result.increment(new RationalFraction(partValue, (long) Math.pow(10, length)));
                fracLength = length;
            } else { // Repeating part
                long commonDenom = (long) Math.pow(10, fracLength);
                commonDenom *= (long) (Math.pow(10, length) - 1);
                result.increment(new RationalFraction(partValue, commonDenom));
            }
        }
        return result;
    }
}

class RationalFraction {
    long num, den;
    RationalFraction(long numerator, long denominator) {
        long gcd = RationalFraction.gcd(numerator, denominator);
        this.num = numerator / gcd;
        this.den = denominator / gcd;
    }

    public void increment(RationalFraction other) {
        long newNum = this.num * other.den + this.den * other.num;
        long newDen = this.den * other.den;
        long gcd = RationalFraction.gcd(newNum, newDen);
        this.num = newNum / gcd;
        this.den = newDen / gcd;
    }

    static long gcd(long a, long b) {
        return b != 0 ? gcd(b % a, a) : a;
    }
}