972. Equal Rational Numbers

public class Solution {
    public bool IsRationalEqual(string S, string T) {
        Fraction f1 = Convert(S);
        Fraction f2 = Convert(T);
        return f1.n == f2.n && f1.d == f2.d;
    }
    public Fraction Convert(string S) {
        int state = 0;
        Fraction ans = new Fraction(0, 1);
        int decimal_size = 0;
        foreach (string part in S.Split(new char[] { '.', '(', ')' })) {
            state++;
            if (string.IsNullOrEmpty(part)) continue;
            long x = long.Parse(part);
            int sz = part.Length;
            if (state == 1) {
                ans.Iadd(new Fraction(x, 1));
            } else if (state == 2) {
                ans.Iadd(new Fraction(x, (long)Math.Pow(10, sz)));
                decimal_size = sz;
            } else {
                long denom = (long)Math.Pow(10, decimal_size);
                denom *= (long)(Math.Pow(10, sz) - 1);
                ans.Iadd(new Fraction(x, denom));
            }
        }
        return ans;
    }
}
public class Fraction {
    public long n, d;
    public Fraction(long n, long d) {
        long g = Gcd(n, d);
        this.n = n / g;
        this.d = d / g;
    }
    public void Iadd(Fraction other) {
        long numerator = this.n * other.d + this.d * other.n;
        long denominator = this.d * other.d;
        long g = Gcd(numerator, denominator);
        this.n = numerator / g;
        this.d = denominator / g;
    }
    public static long Gcd(long x, long y) {
        return x != 0 ? Gcd(y % x, x) : y;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsRationalEqual(string S, string T) {
        Fraction f1 = Convert(S);
        Fraction f2 = Convert(T);
        return f1.n == f2.n && f1.d == f2.d;
    }
    public Fraction Convert(string S) {
        int state = 0;
        Fraction ans = new Fraction(0, 1);
        int decimal_size = 0;
        foreach (string part in S.Split(new char[] { '.', '(', ')' })) {
            state++;
            if (string.IsNullOrEmpty(part)) continue;
            long x = long.Parse(part);
            int sz = part.size();
            if (state == 1) {
                ans.Iadd(new Fraction(x, 1));
            } else if (state == 2) {
                ans.Iadd(new Fraction(x, (long)Math.Pow(10, sz)));
                decimal_size = sz;
            } else {
                long denom = (long)Math.Pow(10, decimal_size);
                denom *= (long)(Math.Pow(10, sz) - 1);
                ans.Iadd(new Fraction(x, denom));
            }
        }
        return ans;
    }
}
public class Fraction {
    public long n, d;
    public Fraction(long n, long d) {
        long g = Gcd(n, d);
        this.n = n / g;
        this.d = d / g;
    }
    public void Iadd(Fraction other) {
        long numerator = this.n * other.d + this.d * other.n;
        long denominator = this.d * other.d;
        long g = Gcd(numerator, denominator);
        this.n = numerator / g;
        this.d = denominator / g;
    }
    public static long Gcd(long x, long y) {
        return x != 0 ? Gcd(y % x, x) : y;
    }
}

class Solution {
    public boolean isRationalEqual(String S, String T) {
        Fraction f1 = convert(S);
        Fraction f2 = convert(T);
        return f1.n == f2.n && f1.d == f2.d;
    }

    public Fraction convert(String S) {
        int state = 0;
        Fraction ans = new Fraction(0, 1);
        int decimal_size = 0;

        for (String part: S.split("[.()]")) {
            state++;
            if (part.isEmpty()) continue;
            long x = Long.valueOf(part);
            int sz = part.length();

            if (state == 1) {
                ans.iadd(new Fraction(x, 1));
            } else if (state == 2) {
                ans.iadd(new Fraction(x, (long) Math.pow(10, sz)));
                decimal_size = sz;
            } else {
                long denom = (long) Math.pow(10, decimal_size);
                denom *= (long) (Math.pow(10, sz) - 1);
                ans.iadd(new Fraction(x, denom));
            }
        }
        return ans;
    }
}

class Fraction {
    long n, d;
    Fraction(long n, long d) {
        long g = gcd(n, d);
        this.n = n / g;
        this.d = d / g;
    }

    public void iadd(Fraction other) {
        long numerator = this.n * other.d + this.d * other.n;
        long denominator = this.d * other.d;
        long g = Fraction.gcd(numerator, denominator);
        this.n = numerator / g;
        this.d = denominator / g;
    }

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

from math import gcd

class Fraction:
    def __init__(self, n, d):
        g = gcd(n, d)
        self.n = n // g
        self.d = d // g

    def iadd(self, other):
        numerator = self.n * other.d + self.d * other.n
        denominator = self.d * other.d
        g = gcd(numerator, denominator)
        self.n = numerator // g
        self.d = denominator // g

class Solution:
    def isRationalEqual(self, S: str, T: str) -> bool:
        f1 = self.convert(S)
        f2 = self.convert(T)
        return f1.n == f2.n and f1.d == f2.d

    def convert(self, S: str) -> Fraction:
        state = 0
        ans = Fraction(0, 1)
        decimal_size = 0

        for part in S.split('.'):
            state += 1
            if not part:
                continue
            x = int(part)
            sz = len(part)

            if state == 1:
                ans.iadd(Fraction(x, 1))
            elif state == 2:
                ans.iadd(Fraction(x, 10 ** sz))
                decimal_size = sz
            else:
                denom = 10 ** decimal_size
                denom *= 10 ** sz - 1
                ans.iadd(Fraction(x, denom))
        return ans

package main

import (
  "math"
  "strconv"
  "strings"
)

type Fraction struct {
  n, d int64
}

func (f *Fraction) iadd(other Fraction) {
  numerator := f.n*other.d + f.d*other.n
  denominator := f.d * other.d
  g := gcd(numerator, denominator)
  f.n = numerator / g
  f.d = denominator / g
}

func gcd(x, y int64) int64 {
  if x != 0 {
    return gcd(y%x, x)
  }
  return y
}

func isRationalEqual(S string, T string) bool {
  f1 := convert(S)
  f2 := convert(T)
  return f1.n == f2.n && f1.d == f2.d
}

func convert(S string) Fraction {
  state := 0
  ans := Fraction{0, 1}
  decimalSize := 0

  parts := strings.FieldsFunc(S, func(r rune) bool {
    return r == '.' || r == '(' || r == ')'
  })

  for _, part := range parts {
    state++
    if part == "" {
      continue
    }
    x, _ := strconv.ParseInt(part, 10, 64)
    sz := len(part)

    if state == 1 {
      ans.iadd(Fraction{x, 1})
    } else if state == 2 {
      ans.iadd(Fraction{x, int64(math.Pow(10, float64(sz)))})
      decimalSize = sz
    } else {
      denom := int64(math.Pow(10, float64(decimalSize)))
      denom *= int64(math.Pow(10, float64(sz)) - 1)
      ans.iadd(Fraction{x, denom})
    }
  }
  return ans
}

func main() {
  // Test the function here
}

Algorithm

Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую number, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.

Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). find значение дроби для повторяющейся части, используя формулу геометрической прогрессии.

Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное number. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения.

😎