Formatted question description: https://leetcode.ca/all/972.html

972. Equal Rational Numbers

Level

Hard

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.

In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:

  • <IntegerPart> (e.g. 0, 12, 123)
  • <IntegerPart><.><NonRepeatingPart> (e.g. 0.5, 1., 2.12, 2.0001)
  • <IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)> (e.g. 0.1(6), 0.9(9), 0.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)

Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.

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) = “”.

Note:

  1. Each part consists only of digits.
  2. The <IntegerPart> will not begin with 2 or more zeros. (There is no other restriction on the digits of each part.)
  3. 1 <= <IntegerPart>.length <= 4
  4. 0 <= <NonRepeatingPart>.length <= 4
  5. 1 <= <RepeatingPart>.length <= 4

Solution

For both strings S and T, convert each number into a rational number, which contains a numerator and a denominator.

To convert a string to a rational number, consider the following cases.

  1. The string only contains the integer part. If the decimal point exists, remove the decimal point. Set the numerator to be the integer part and the denominator to be 1. For example, 12 is represented as 12/1.

  2. The string represents a decimal with no repeating parts. For example, 2.12 has an integer part 2 and a decimal part 0.12. The decimal part can be represented as 12/100, and the result of fraction reduction is 3/25. Adding the integer part to the rational number and the result is 53/25.

  3. The string represents a repeating decimal. Consider the following two cases. 3.1. Only the repeating part exists. For example, 1.(142857) has an integer part 1 and a decimal part 0.(142857), The decimal part can be represented as 142857/999999, and the result of fraction reduction is 1/7. Adding the integer part to the rational number and the result is 8/7. 3.2 Both the non-repeating part and the repeating part exist. For example, 3.1(3) has an integer part 3 and a decimal part 0.1(3). The decimal part can be represented by (13-1)/90 = 12/90, and the result of fraction reduction is 2/15. Adding the integer part to the rational number and the result is 47/15.

After converting both strings to rational numbers, check whether the two rational numbers’ numerators are the same and denominators are the same.

class Solution {
    public boolean isRationalEqual(String S, String T) {
        int[] rationalS = getRational(S);
        int[] rationalT = getRational(T);
        return rationalS[0] == rationalT[0] && rationalS[1] == rationalT[1];
    }

    public int[] getRational(String str) {
        boolean positive = true;
        if (str.charAt(0) == '-') {
            str = str.substring(1);
            positive = false;
        }
        int dotIndex = str.indexOf('.');
        if (dotIndex < 0) {
            int integer = Integer.parseInt(str);
            if (!positive)
                integer = -integer;
            int[] rational = {integer, 1};
            return rational;
        }
        int length = str.length();
        if (dotIndex == length - 1) {
            int integer = Integer.parseInt(str.substring(0, dotIndex));
            if (!positive)
                integer = -integer;
            int[] rational = {integer, 1};
            return rational;
        }
        String integerPart = str.substring(0, dotIndex);
        int integer = Integer.parseInt(integerPart);
        String decimalPart = str.substring(dotIndex + 1);
        int decimalPartLength = length - dotIndex - 1;
        int repeatingIndex = str.indexOf('(');
        if (repeatingIndex < 0) {
            int numerator = Integer.parseInt(decimalPart);
            int denominator = (int) Math.pow(10, decimalPartLength);
            int gcd = gcd(numerator, denominator);
            numerator /= gcd;
            denominator /= gcd;
            int[] rational = {numerator, denominator};
            rational[0] += integer * denominator;
            if (!positive)
                rational[0] = -rational[0];
            return rational;
        } else {
            if (repeatingIndex - dotIndex == 1) {
                int numerator = Integer.parseInt(str.substring(repeatingIndex + 1, length - 1));
                int denominator = (int) Math.pow(10, decimalPartLength - 2) - 1;
                int gcd = gcd(numerator, denominator);
                numerator /= gcd;
                denominator /= gcd;
                int[] rational = {numerator, denominator};
                rational[0] += integer * denominator;
                if (!positive)
                    rational[0] = -rational[0];
                return rational;
            } else {
                int nonRepeatingLength = repeatingIndex - dotIndex - 1;
                int repeatingLength = length - 2 - repeatingIndex;
                int nonRepeating = Integer.parseInt(str.substring(dotIndex + 1, repeatingIndex));
                int numerator = nonRepeating * (int) Math.pow(10, repeatingLength) + Integer.parseInt(str.substring(repeatingIndex + 1, length - 1)) - nonRepeating;
                int denominator = (int) (Math.pow(10, repeatingLength) - 1) * (int) (Math.pow(10, nonRepeatingLength));
                int gcd = gcd(numerator, denominator);
                numerator /= gcd;
                denominator /= gcd;
                int[] rational = {numerator, denominator};
                rational[0] += integer * denominator;
                if (!positive)
                    rational[0] = -rational[0];
                return rational;
            }
        }
    }

    public int gcd(int a, int b) {
        if (a == 0 && b == 0)
            return 1;
        while (a > 0 && b > 0) {
            if (a > b) {
                int temp = a;
                a = b;
                b = temp;
            }
            b %= a;
        }
        return a == 0 ? b : a;
    }
}

All Problems

All Solutions