972. Equal Rational Numbers
Problem Explanation
The problem states that you have two strings, which represent a non-negative rational number. The task is to figure out if both these strings represent the same number or not. Basically, the problem requires comparing two rational numbers which are represented in string format. The rational number itself is expressed in three different ways.
- Only the integer part. For example - "123"
- An integer followed by a decimal and a non-repeating part. For example - "123.456"
- An integer followed by a decimal, a non-repeating part and a repeating part in parentheses. For example - "123.456(789)"
We need to evaluate these strings and compare their floating numbers. Due to the repeating part, the evaluation of the third type of number can be tricky.
Taking an example - Let's say the two strings are "0.1(6)" and "0.1666(6)".
String 1 -> "0.1(6)": This represents the number 0.1666... String 2 -> "0.1666(6)": As already mentioned this represents 0.1666..., so both represent the same number.
Therefore the evaluation is True.
Solution Approach
The approach for the solution for this problem involve converting both strings into floating numbers and then comparing them. The solution uses simple string manipulation methods to convert these strings into actual float numbers.
The function valueOf()
computes the floating number represented by the string. We get the slice of the string before the occurrence of parentheses (if any) and convert it to a double number. Then, calculate the repeating part of the string (if any), multiply it by the appropriate ratio according to its length, and add it to the previous double number. Finally, we compare the float values by checking if the absolute difference is less than a very small number (1e-9) as we're dealing with floating point precision.
Implementation
C++
cpp
class Solution {
public:
bool isRationalEqual(string s, string t) {
return abs(valueOf(s) - valueOf(t)) < 1e-9;
}
private:
const static vector<double> ratios{1.0, 1.0 / 9, 1.0 / 99, 1.0 / 999,
1.0 / 9999};
double valueOf(const string& s) {
if (s.find('(') == string::npos)
return stod(s); // stod function converts string to double
const int leftParenIndex = s.find_first_of('(');
const int rightParenIndex = s.find_first_of(')');
const int dotIndex = s.find_first_of('.');
const double integerAndNonRepeating = stod(s.substr(0, leftParenIndex)); // Get the non-repeating string part and convert to double
const int nonRepeatingLength = leftParenIndex - dotIndex - 1;
const int repeating = stoi(s.substr(leftParenIndex + 1, rightParenIndex - leftParenIndex - 1)); // Get the repeating string part and convert to integer
const int repeatingLength = rightParenIndex - leftParenIndex - 1;
return integerAndNonRepeating +
repeating * pow(0.1, nonRepeatingLength) * ratios[repeatingLength]; // Compute the total number by adding non-repeating part to the repeating part multiplied by the appropriate power of 0.1 and the ratio corresponding to its length
}
};
Python
python class Solution: def isRationalEqual(self, s: str, t: str) -> bool: def value(s): if '(' not in s: return float(s) i = s.index('(') nonRepeating, repeating = s[:i], s[i + 1:-1] return float(nonRepeating) + float(repeating) / (10 ** len(repeating) - 1) / 10 ** (i - s.index('.') - 1) return abs(value(s) - value(t)) < 1e-9
In this code, we first define a function value()
which will convert the string into a floating number. If there's no repeating part in the string, Pythonās inbuilt function is sufficient and directly converts the string to a floating number. However, if it contains a repeating part, we divide the section inside the parentheses by the number of nines equal to the length of the repeating string and the appropriate power of ten. Finally, we subtract the resulting floating number from s
and check if it's less than a very small number (1e-9)
JavaScript
javascript
const isRationalEqual = (s, t) => {
return Math.abs(valueOf(s) - valueOf(t)) < 1e-9;
}
const valueOf = (s) => {
let leftParenIndex = s.indexOf('(');
if (leftParenIndex === -1) {
return parseFloat(s);
}
let rightParenIndex = s.indexOf(')');
let dotIndex = s.indexOf('.');
let nonRepeating = parseFloat(s.substring(0, leftParenIndex));
let nonRepeatingLength = leftParenIndex - dotIndex - 1;
let repeating = parseInt(s.substring(leftParenIndex + 1, rightParenIndex));
let repeatingLength = rightParenIndex - leftParenIndex - 1;
return nonRepeating +
repeating * Math.pow(0.1, nonRepeatingLength) * (1.0 / (Math.pow(10, repeatingLength) - 1))
}
In JavaScript, we're implementing a similar strategy. If string s
doesn't contain a repeating part, we parse it as a float. If it does, we slice the non-repeating and the repeating part of the string. The non-repeating part is parsed to a float and the repeating part to an int. Then, we calculate the sum of the non-repeating part plus the repeating part divided by 10 ^ repeatingLength - 1
.
Java
java
class Solution {
public boolean isRationalEqual(String S, String T) {
return Math.abs(value(S) - value(T)) < 1E-9;
}
public double value(String S) {
int i = S.indexOf("(");
if (i > 0) {
String base = S.substring(0, i);
String rep = S.substring(i + 1, S.length() - 1);
for (int j = 0; j < 20; ++j) base += rep;
return Double.valueOf(base);
} else {
return Double.valueOf(S);
}
}
}
In the Java solution, we convert the string to a double value. If the string includes a repeating part, we append the repeating part 20 times to the non-repeating part to approximate the repeating decimal.
The boolean value is then calculated by taking the absolute value of the difference between the two converted floating-point numbers and checking whether it is smaller than a very small number (1e-9), which would mean they are essentially the same number.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorYou are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!