Dadas dos strings S y T que representan números racionales no negativos , la tarea es comprobar si los valores de S y T son iguales o no. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba “NO” .
Nota: Cualquier número racional se puede representar de una de las tres formas siguientes:
- <IntegerPart> (por ejemplo, 0, 12, 123)
- <IntegerPart><.><NonRepeatingPart> (por ejemplo, 0.5, 1., 2.12, 2.0001)
- <ParteEntero><.><ParteNoRepetida><(><ParteRepetida><)> (por ejemplo, 0.1(6), 0.9(9), 0.00(1212))
Ejemplos:
Entrada: S = “0.(52)”, T = “0.5(25)”
Salida: SI
Explicación:
El número racional “0.(52)” se puede representar como 0.52525252…
El número racional “0.5(25)” se puede representar como 0.525252525….
Por lo tanto, la salida requerida es «SÍ».Entrada: S = “0.9(9)”, T = “1”.
Salida: SI
Explicación:
El número racional “0.9(9)” se puede representar como 0.999999999…, es igual a 1.
El número racional “1”. se puede representar como el número 1.
Por lo tanto, la salida requerida es «SÍ».
Enfoque: La idea es convertir los números racionales en fracciones y luego verificar si las fracciones de ambos números racionales son iguales o no . Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba “NO” . Las siguientes son las observaciones:
La parte repetida de una expansión decimal se denota convencionalmente dentro de un par de corchetes.
Por ejemplo: 1/6 = 0,16666666… = 0,1(6) = 0,1666(6) = 0,166(66)
Tanto 0,1(6) como 0,1666(6) o 0,166(66) son representaciones correctas de 1/6.
Cualquier número racional se puede convertir en fracciones según las siguientes observaciones:
Sea x = 0.5(25) —> (1)
Parte entera = 0, Parte no repetida = 5, Parte repetida = 25
Multiplique ambos lados de la ecuación (1) por 10 elevado a la potencia de la longitud de la parte no repetida, es decir, 10 * x = 5.(25) —> (2)
Multiplica ambos lados de la ecuación (1) por 10 elevado a la potencia de (longitud de la parte que no se repite + longitud de la parte que se repite), 1000 * x = 525. (25) —> (3)
Reste la ecuación (2) de la ecuación (3)
1000 * x – 10 * x = 525.(25)-5.(25)
990 * x = 520
⇒ x = 520 / 990
Siga los pasos a continuación para resolver el problema:
- Convierta ambos números racionales en fracciones usando las observaciones anteriores.
- Comprueba si ambas fracciones de los números son iguales o no . Si se encuentra que es cierto, escriba «SÍ» .
- De lo contrario, escriba “NO” .
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to check if the string S and T
// are equal or not
public static boolean isRationalEqual(String s,
String t)
{
// Stores the fractional part of s
Fraction f1 = Rational.parse(s).toFraction();
// Stores the fractional part of t
Fraction f2 = Rational.parse(t).toFraction();
// If the condition satisfies, returns true
// otherwise return false
return f1.p * f2.q == f2.p * f1.q;
}
// Rational class having integer, non-repeating
// and repeating part of the number
public static class Rational {
private final String integer, nonRepeating,
repeating;
// Constructor function to initialize
// the object of the class
private Rational(String integer,
String nonRepeating,
String repeating)
{
// Stores integer part
this.integer = integer;
// Stores non repeating part
this.nonRepeating = nonRepeating;
// Stores repeating part
this.repeating = repeating;
}
// Function to split the string into
// integer, repeating & non-repeating part
public static Rational parse(String s)
{
// Split s into parts
String[] parts = s.split("[.()]");
return new Rational(
parts.length >= 1 ? parts[0] : "",
parts.length >= 2 ? parts[1] : "",
parts.length >= 3 ? parts[2] : "");
}
// Function to convert the string
// into fraction
public Fraction toFraction()
{
long a = tenpow(nonRepeating.length());
long i = Long.parseLong(integer + nonRepeating);
// If there is no repeating part, then
// form a new fraction of the form i/a
if (repeating.length() == 0) {
return new Fraction(i, a);
}
// Otherwise
else {
long b = tenpow(nonRepeating.length()
+ repeating.length());
long j = Long.parseLong(
integer + nonRepeating + repeating);
// Form the new Fraction and return
return new Fraction(j - i, b - a);
}
}
public String toString()
{
return String.format("%s.%s(%s)", integer,
nonRepeating, repeating);
}
}
// Fraction class having numerator as p
// and denominator as q
public static class Fraction {
private final long p, q;
// Constructor function to initialize
// the object of the class
private Fraction(long p, long q)
{
this.p = p;
this.q = q;
}
public String toString()
{
return String.format("%d/%d", p, q);
}
}
// Function to find 10 raised
// to power of x
public static long tenpow(int x)
{
assert x >= 0;
long r = 1;
while (--x >= 0) {
r *= 10;
}
return r;
}
// Driver Code
public static void main(String[] args)
{
// Given S and T
String S = "0.(52)", T = "0.5(25)";
// Function Call
if (isRationalEqual(S, T)) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
// Print result
}
}
YES
Complejidad de Tiempo: O(N), donde N es la longitud máxima de S y T
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA