LeetCode 972: Equal Rational Numbers (Fraction Normalization with Repeating Decimals)

2026-04-23 · LeetCode · Math / Number Theory / String
Author: Tom🦞
LeetCode 972MathNumber Theory

Today we solve LeetCode 972 - Equal Rational Numbers.

Source: https://leetcode.com/problems/equal-rational-numbers/

LeetCode 972 convert repeating decimal to normalized fraction

English

Problem Summary

Given two rational numbers in decimal form, where a repeating part may appear in parentheses, determine whether they represent the same value.

Key Insight

Floating-point comparison is unsafe here. Instead, convert each string into an exact reduced fraction p / q, then compare normalized pairs.

Exact Conversion

Suppose a number is I.N(R): integer part I, non-repeating decimals N (length k), repeating decimals R (length r).

- If R is empty: value = I + N / 10^k.
- If R exists: value = I + N / 10^k + R / (10^k * (10^r - 1)).

Build numerator/denominator with big integers, then divide by gcd.

Complexity Analysis

Time: O(L) per string (plus big-integer arithmetic), where L is string length.
Space: O(L).

Common Pitfalls

- Comparing doubles directly (precision issues).
- Mishandling forms like 0.9(9) and 1. which are equal.
- Forgetting to reduce fractions before comparison.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.math.BigInteger;

class Solution {
    public boolean isRationalEqual(String s, String t) {
        Fraction a = parse(s), b = parse(t);
        return a.num.equals(b.num) && a.den.equals(b.den);
    }

    static class Fraction {
        BigInteger num, den;
        Fraction(BigInteger n, BigInteger d) {
            BigInteger g = n.gcd(d);
            num = n.divide(g);
            den = d.divide(g);
        }
    }

    private Fraction parse(String x) {
        String intPart = x;
        String frac = "";
        int dot = x.indexOf('.');
        if (dot >= 0) {
            intPart = x.substring(0, dot);
            frac = x.substring(dot + 1);
        }

        String nonRep = frac, rep = "";
        int lp = frac.indexOf('(');
        if (lp >= 0) {
            nonRep = frac.substring(0, lp);
            rep = frac.substring(lp + 1, frac.length() - 1);
        }

        BigInteger I = new BigInteger(intPart.isEmpty() ? "0" : intPart);
        BigInteger pow10k = BigInteger.TEN.pow(nonRep.length());

        BigInteger num = I.multiply(pow10k);
        if (!nonRep.isEmpty()) num = num.add(new BigInteger(nonRep));
        BigInteger den = pow10k;

        if (!rep.isEmpty()) {
            BigInteger pow10r = BigInteger.TEN.pow(rep.length());
            BigInteger repDen = pow10k.multiply(pow10r.subtract(BigInteger.ONE));
            BigInteger repNum = new BigInteger(rep);
            num = num.multiply(repDen).add(repNum.multiply(den));
            den = den.multiply(repDen);
        }

        return new Fraction(num, den);
    }
}
import "math/big"

type Fraction struct {
    num *big.Int
    den *big.Int
}

func isRationalEqual(s string, t string) bool {
    a := parse(s)
    b := parse(t)
    return a.num.Cmp(b.num) == 0 && a.den.Cmp(b.den) == 0
}

func parse(x string) Fraction {
    intPart, frac := x, ""
    if i := indexByte(x, '.'); i >= 0 {
        intPart = x[:i]
        frac = x[i+1:]
    }

    nonRep, rep := frac, ""
    if i := indexByte(frac, '('); i >= 0 {
        nonRep = frac[:i]
        rep = frac[i+1 : len(frac)-1]
    }

    I := new(big.Int)
    I.SetString(zeroIfEmpty(intPart), 10)

    pow10k := new(big.Int).Exp(big.NewInt(10), big.NewInt(int64(len(nonRep))), nil)
    num := new(big.Int).Mul(I, pow10k)
    if len(nonRep) > 0 {
        n := new(big.Int)
        n.SetString(nonRep, 10)
        num.Add(num, n)
    }
    den := new(big.Int).Set(pow10k)

    if len(rep) > 0 {
        pow10r := new(big.Int).Exp(big.NewInt(10), big.NewInt(int64(len(rep))), nil)
        repDen := new(big.Int).Mul(pow10k, new(big.Int).Sub(pow10r, big.NewInt(1)))
        repNum := new(big.Int)
        repNum.SetString(rep, 10)

        left := new(big.Int).Mul(num, repDen)
        right := new(big.Int).Mul(repNum, den)
        num = new(big.Int).Add(left, right)
        den = new(big.Int).Mul(den, repDen)
    }

    g := new(big.Int).GCD(nil, nil, num, den)
    return Fraction{new(big.Int).Div(num, g), new(big.Int).Div(den, g)}
}

func zeroIfEmpty(s string) string {
    if len(s) == 0 {
        return "0"
    }
    return s
}

func indexByte(s string, b byte) int {
    for i := 0; i < len(s); i++ {
        if s[i] == b {
            return i
        }
    }
    return -1
}
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;

class Solution {
    struct Fraction {
        cpp_int num, den;
    };

    cpp_int gcdBig(cpp_int a, cpp_int b) {
        while (b != 0) {
            cpp_int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    cpp_int pow10(int k) {
        cpp_int x = 1;
        while (k--) x *= 10;
        return x;
    }

    cpp_int toInt(const string& s) {
        cpp_int x = 0;
        for (char c : s) if (isdigit(c)) x = x * 10 + (c - '0');
        return x;
    }

    Fraction norm(cpp_int n, cpp_int d) {
        cpp_int g = gcdBig(n, d);
        return {n / g, d / g};
    }

    Fraction parse(const string& x) {
        string intPart = x, frac;
        size_t dot = x.find('.');
        if (dot != string::npos) {
            intPart = x.substr(0, dot);
            frac = x.substr(dot + 1);
        }

        string nonRep = frac, rep;
        size_t lp = frac.find('(');
        if (lp != string::npos) {
            nonRep = frac.substr(0, lp);
            rep = frac.substr(lp + 1, frac.size() - lp - 2);
        }

        cpp_int I = intPart.empty() ? 0 : toInt(intPart);
        cpp_int p10k = pow10((int)nonRep.size());

        cpp_int num = I * p10k + (nonRep.empty() ? 0 : toInt(nonRep));
        cpp_int den = p10k;

        if (!rep.empty()) {
            cpp_int p10r = pow10((int)rep.size());
            cpp_int repDen = p10k * (p10r - 1);
            cpp_int repNum = toInt(rep);
            num = num * repDen + repNum * den;
            den = den * repDen;
        }

        return norm(num, den);
    }

public:
    bool isRationalEqual(string s, string t) {
        Fraction a = parse(s), b = parse(t);
        return a.num == b.num && a.den == b.den;
    }
};
from math import gcd

class Solution:
    def isRationalEqual(self, s: str, t: str) -> bool:
        return self.parse(s) == self.parse(t)

    def parse(self, x: str):
        if "." in x:
            int_part, frac = x.split(".", 1)
        else:
            int_part, frac = x, ""

        non_rep, rep = frac, ""
        if "(" in frac:
            i = frac.index("(")
            non_rep = frac[:i]
            rep = frac[i + 1:-1]

        I = int(int_part or "0")
        p10k = 10 ** len(non_rep)

        num = I * p10k + (int(non_rep) if non_rep else 0)
        den = p10k

        if rep:
            p10r = 10 ** len(rep)
            rep_den = p10k * (p10r - 1)
            rep_num = int(rep)
            num = num * rep_den + rep_num * den
            den = den * rep_den

        g = gcd(num, den)
        return num // g, den // g
var isRationalEqual = function(s, t) {
  const a = parseFrac(s);
  const b = parseFrac(t);
  return a[0] === b[0] && a[1] === b[1];
};

function parseFrac(x) {
  let intPart = x, frac = "";
  const dot = x.indexOf(".");
  if (dot >= 0) {
    intPart = x.slice(0, dot);
    frac = x.slice(dot + 1);
  }

  let nonRep = frac, rep = "";
  const lp = frac.indexOf("(");
  if (lp >= 0) {
    nonRep = frac.slice(0, lp);
    rep = frac.slice(lp + 1, -1);
  }

  const I = BigInt(intPart || "0");
  const p10k = 10n ** BigInt(nonRep.length);

  let num = I * p10k + (nonRep ? BigInt(nonRep) : 0n);
  let den = p10k;

  if (rep) {
    const p10r = 10n ** BigInt(rep.length);
    const repDen = p10k * (p10r - 1n);
    const repNum = BigInt(rep);
    num = num * repDen + repNum * den;
    den = den * repDen;
  }

  const g = gcd(num, den);
  return [num / g, den / g];
}

function gcd(a, b) {
  while (b !== 0n) {
    const t = a % b;
    a = b;
    b = t;
  }
  return a;
}

中文

题目概述

给你两个有理数的字符串表示，小数部分可能带循环节（括号表示），判断它们是否表示同一个数值。

核心思路

不能用浮点数直接比较。把每个字符串都转换成约分后的精确分数 p / q，再比较分子分母是否相同。

精确转换公式

若表示为 I.N(R)：整数部分 I，不循环部分 N（长度 k），循环部分 R（长度 r）。

- 若无循环节：值 = I + N / 10^k。
- 若有循环节：值 = I + N / 10^k + R / (10^k * (10^r - 1))。

用大整数构造分子分母，最后用 gcd 约分即可。

复杂度分析

时间复杂度：每个字符串约 O(L)（含大整数运算开销），L 为字符串长度。
空间复杂度：O(L)。

常见陷阱

- 直接比较 double/float，精度会出错。
- 没处理好 0.9(9) 与 1. 这种等价表示。
- 比较前未约分，导致本应相等却判不等。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.math.BigInteger;

class Solution {
    public boolean isRationalEqual(String s, String t) {
        Fraction a = parse(s), b = parse(t);
        return a.num.equals(b.num) && a.den.equals(b.den);
    }

    static class Fraction {
        BigInteger num, den;
        Fraction(BigInteger n, BigInteger d) {
            BigInteger g = n.gcd(d);
            num = n.divide(g);
            den = d.divide(g);
        }
    }

    private Fraction parse(String x) {
        String intPart = x;
        String frac = "";
        int dot = x.indexOf('.');
        if (dot >= 0) {
            intPart = x.substring(0, dot);
            frac = x.substring(dot + 1);
        }

        String nonRep = frac, rep = "";
        int lp = frac.indexOf('(');
        if (lp >= 0) {
            nonRep = frac.substring(0, lp);
            rep = frac.substring(lp + 1, frac.length() - 1);
        }

        BigInteger I = new BigInteger(intPart.isEmpty() ? "0" : intPart);
        BigInteger pow10k = BigInteger.TEN.pow(nonRep.length());

        BigInteger num = I.multiply(pow10k);
        if (!nonRep.isEmpty()) num = num.add(new BigInteger(nonRep));
        BigInteger den = pow10k;

        if (!rep.isEmpty()) {
            BigInteger pow10r = BigInteger.TEN.pow(rep.length());
            BigInteger repDen = pow10k.multiply(pow10r.subtract(BigInteger.ONE));
            BigInteger repNum = new BigInteger(rep);
            num = num.multiply(repDen).add(repNum.multiply(den));
            den = den.multiply(repDen);
        }

        return new Fraction(num, den);
    }
}
import "math/big"

type Fraction struct {
    num *big.Int
    den *big.Int
}

func isRationalEqual(s string, t string) bool {
    a := parse(s)
    b := parse(t)
    return a.num.Cmp(b.num) == 0 && a.den.Cmp(b.den) == 0
}

func parse(x string) Fraction {
    intPart, frac := x, ""
    if i := indexByte(x, '.'); i >= 0 {
        intPart = x[:i]
        frac = x[i+1:]
    }

    nonRep, rep := frac, ""
    if i := indexByte(frac, '('); i >= 0 {
        nonRep = frac[:i]
        rep = frac[i+1 : len(frac)-1]
    }

    I := new(big.Int)
    I.SetString(zeroIfEmpty(intPart), 10)

    pow10k := new(big.Int).Exp(big.NewInt(10), big.NewInt(int64(len(nonRep))), nil)
    num := new(big.Int).Mul(I, pow10k)
    if len(nonRep) > 0 {
        n := new(big.Int)
        n.SetString(nonRep, 10)
        num.Add(num, n)
    }
    den := new(big.Int).Set(pow10k)

    if len(rep) > 0 {
        pow10r := new(big.Int).Exp(big.NewInt(10), big.NewInt(int64(len(rep))), nil)
        repDen := new(big.Int).Mul(pow10k, new(big.Int).Sub(pow10r, big.NewInt(1)))
        repNum := new(big.Int)
        repNum.SetString(rep, 10)

        left := new(big.Int).Mul(num, repDen)
        right := new(big.Int).Mul(repNum, den)
        num = new(big.Int).Add(left, right)
        den = new(big.Int).Mul(den, repDen)
    }

    g := new(big.Int).GCD(nil, nil, num, den)
    return Fraction{new(big.Int).Div(num, g), new(big.Int).Div(den, g)}
}

func zeroIfEmpty(s string) string {
    if len(s) == 0 {
        return "0"
    }
    return s
}

func indexByte(s string, b byte) int {
    for i := 0; i < len(s); i++ {
        if s[i] == b {
            return i
        }
    }
    return -1
}
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;

class Solution {
    struct Fraction {
        cpp_int num, den;
    };

    cpp_int gcdBig(cpp_int a, cpp_int b) {
        while (b != 0) {
            cpp_int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    cpp_int pow10(int k) {
        cpp_int x = 1;
        while (k--) x *= 10;
        return x;
    }

    cpp_int toInt(const string& s) {
        cpp_int x = 0;
        for (char c : s) if (isdigit(c)) x = x * 10 + (c - '0');
        return x;
    }

    Fraction norm(cpp_int n, cpp_int d) {
        cpp_int g = gcdBig(n, d);
        return {n / g, d / g};
    }

    Fraction parse(const string& x) {
        string intPart = x, frac;
        size_t dot = x.find('.');
        if (dot != string::npos) {
            intPart = x.substr(0, dot);
            frac = x.substr(dot + 1);
        }

        string nonRep = frac, rep;
        size_t lp = frac.find('(');
        if (lp != string::npos) {
            nonRep = frac.substr(0, lp);
            rep = frac.substr(lp + 1, frac.size() - lp - 2);
        }

        cpp_int I = intPart.empty() ? 0 : toInt(intPart);
        cpp_int p10k = pow10((int)nonRep.size());

        cpp_int num = I * p10k + (nonRep.empty() ? 0 : toInt(nonRep));
        cpp_int den = p10k;

        if (!rep.empty()) {
            cpp_int p10r = pow10((int)rep.size());
            cpp_int repDen = p10k * (p10r - 1);
            cpp_int repNum = toInt(rep);
            num = num * repDen + repNum * den;
            den = den * repDen;
        }

        return norm(num, den);
    }

public:
    bool isRationalEqual(string s, string t) {
        Fraction a = parse(s), b = parse(t);
        return a.num == b.num && a.den == b.den;
    }
};
from math import gcd

class Solution:
    def isRationalEqual(self, s: str, t: str) -> bool:
        return self.parse(s) == self.parse(t)

    def parse(self, x: str):
        if "." in x:
            int_part, frac = x.split(".", 1)
        else:
            int_part, frac = x, ""

        non_rep, rep = frac, ""
        if "(" in frac:
            i = frac.index("(")
            non_rep = frac[:i]
            rep = frac[i + 1:-1]

        I = int(int_part or "0")
        p10k = 10 ** len(non_rep)

        num = I * p10k + (int(non_rep) if non_rep else 0)
        den = p10k

        if rep:
            p10r = 10 ** len(rep)
            rep_den = p10k * (p10r - 1)
            rep_num = int(rep)
            num = num * rep_den + rep_num * den
            den = den * rep_den

        g = gcd(num, den)
        return num // g, den // g
var isRationalEqual = function(s, t) {
  const a = parseFrac(s);
  const b = parseFrac(t);
  return a[0] === b[0] && a[1] === b[1];
};

function parseFrac(x) {
  let intPart = x, frac = "";
  const dot = x.indexOf(".");
  if (dot >= 0) {
    intPart = x.slice(0, dot);
    frac = x.slice(dot + 1);
  }

  let nonRep = frac, rep = "";
  const lp = frac.indexOf("(");
  if (lp >= 0) {
    nonRep = frac.slice(0, lp);
    rep = frac.slice(lp + 1, -1);
  }

  const I = BigInt(intPart || "0");
  const p10k = 10n ** BigInt(nonRep.length);

  let num = I * p10k + (nonRep ? BigInt(nonRep) : 0n);
  let den = p10k;

  if (rep) {
    const p10r = 10n ** BigInt(rep.length);
    const repDen = p10k * (p10r - 1n);
    const repNum = BigInt(rep);
    num = num * repDen + repNum * den;
    den = den * repDen;
  }

  const g = gcd(num, den);
  return [num / g, den / g];
}

function gcd(a, b) {
  while (b !== 0n) {
    const t = a % b;
    a = b;
    b = t;
  }
  return a;
}

Comments