Equal Rational Numbers

hard math fraction repeating decimal

Problem

Given two strings s and t, each representing a non-negative rational number, return true if and only if they represent the same number. Each string may contain an integer part, a non-repeating decimal part, and a repeating decimal part enclosed in parentheses, for example 0.1(6) meaning 0.16666….

Inputs = "0.1(6)", t = "0.1666(6)"

Outputtrue

Both equal 1/6, so the answer is true.

from fractions import Fraction

def is_rational_equal(s: str, t: str) -> bool:
    def parse(x):
        if '(' not in x:
            return Fraction(x)
        head, rep = x.split('(')
        rep = rep[:-1]                      # drop ')'
        base = Fraction(head)               # integer + non-repeating part
        d = len(head.split('.')[1])         # digits after the point
        # repeating block of length L starts at scale 10^d
        L = len(rep)
        repeat = Fraction(int(rep), (10 ** L - 1)) / (10 ** d)
        return base + repeat
    return parse(s) == parse(t)

function gcd(a, b) { return b === 0n ? a : gcd(b, a % b); }

function toFraction(x) {
  // returns [num, den] as BigInt, fully reduced
  let num, den;
  const paren = x.indexOf('(');
  const core = paren === -1 ? x : x.slice(0, paren);
  const dot = core.indexOf('.');
  const intPart = dot === -1 ? core : core.slice(0, dot);
  const frac = dot === -1 ? '' : core.slice(dot + 1);
  const d = BigInt(frac.length);
  // base value = (intPart followed by frac) / 10^d
  let baseNum = BigInt((intPart || '0') + frac);
  let baseDen = 10n ** d;
  if (paren === -1) { num = baseNum; den = baseDen; }
  else {
    const rep = x.slice(paren + 1, -1);
    const L = BigInt(rep.length);
    // repeat = rep / (10^L - 1) / 10^d
    const rNum = BigInt(rep);
    const rDen = (10n ** L - 1n) * baseDen;
    num = baseNum * rDen + rNum * baseDen;
    den = baseDen * rDen;
  }
  const g = gcd(num < 0n ? -num : num, den) || 1n;
  return [num / g, den / g];
}

function isRationalEqual(s, t) {
  const [a, b] = toFraction(s), [c, d] = toFraction(t);
  return a * d === c * b;
}

import java.math.BigInteger;

class Solution {
    long[] toFraction(String x) {        // {num, den}
        int paren = x.indexOf('(');
        String core = paren == -1 ? x : x.substring(0, paren);
        int dot = core.indexOf('.');
        String intPart = dot == -1 ? core : core.substring(0, dot);
        String frac = dot == -1 ? "" : core.substring(dot + 1);
        long d = frac.length();
        long baseNum = Long.parseLong((intPart.isEmpty() ? "0" : intPart) + frac);
        long baseDen = (long) Math.pow(10, d);
        long num, den;
        if (paren == -1) { num = baseNum; den = baseDen; }
        else {
            String rep = x.substring(paren + 1, x.length() - 1);
            long L = rep.length();
            long rNum = Long.parseLong(rep);
            long rDen = ((long) Math.pow(10, L) - 1) * baseDen;
            num = baseNum * rDen + rNum * baseDen;
            den = baseDen * rDen;
        }
        long g = BigInteger.valueOf(num).gcd(BigInteger.valueOf(den)).longValue();
        return new long[]{ num / g, den / g };
    }

    public boolean isRationalEqual(String s, String t) {
        long[] a = toFraction(s), b = toFraction(t);
        return a[0] * b[1] == b[0] * a[1];
    }
}

#include <numeric>
#include <string>
using namespace std;

array<long long, 2> toFraction(const string& x) {
    auto paren = x.find('(');
    string core = paren == string::npos ? x : x.substr(0, paren);
    auto dot = core.find('.');
    string intPart = dot == string::npos ? core : core.substr(0, dot);
    string frac = dot == string::npos ? "" : core.substr(dot + 1);
    long long d = frac.size();
    long long baseNum = stoll((intPart.empty() ? "0" : intPart) + frac);
    long long baseDen = 1; for (int k = 0; k < d; k++) baseDen *= 10;
    long long num, den;
    if (paren == string::npos) { num = baseNum; den = baseDen; }
    else {
        string rep = x.substr(paren + 1, x.size() - paren - 2);
        long long pw = 1; for (size_t k = 0; k < rep.size(); k++) pw *= 10;
        long long rNum = stoll(rep);
        long long rDen = (pw - 1) * baseDen;
        num = baseNum * rDen + rNum * baseDen;
        den = baseDen * rDen;
    }
    long long g = __gcd(num, den); if (g == 0) g = 1;
    return { num / g, den / g };
}

bool isRationalEqual(string s, string t) {
    auto a = toFraction(s), b = toFraction(t);
    return a[0] * b[1] == b[0] * a[1];
}

Explanation

Comparing decimals as floating-point numbers is risky because of rounding. The safe trick is to turn each string into an exact fraction and then compare the fractions. Python's Fraction type keeps everything exact.

The parse helper splits the string into an integer-plus-non-repeating part (head) and a repeating block (rep) inside the parentheses. If there is no (, the string is an ordinary decimal and Fraction(x) handles it directly.

For the repeating part we use the classic formula for a repeating decimal: a block of L digits repeating forever equals rep / (10^L - 1). We then divide by 10^d to shift it past the d non-repeating digits, and add it to the base.

Once both strings are fractions, we just check parse(s) == parse(t). Because fractions are exact and automatically reduced, equal values compare equal.

Example: 0.1(6) means 0.1666…. The base is 1/10 and the repeat is 6/9 / 10 = 1/15, giving 1/10 + 1/15 = 1/6. Since 0.1666(6) also reduces to 1/6, the answer is true.

Time: O(L) Space: O(1)