Equal Rational Numbers - Leetcode Solution

Problem Statement: Given two strings representing two rational numbers, you need to return a string representing their sum in the form of a rational number. If the answer is an integer, it should be represented as a string. If the answer is a decimal fraction, it should be represented as a string without extra zeros at the end. If the answer is a negative number, it should begin with ‘-‘. No leading zeros are allowed in the fractional part of a number.

Example:

Input: num1 = "1/2", num2 = "2/3" Output: "7/6" Explanation: 1/2 + 2/3 = 3/6 + 4/6 = 7/6 Input: num1 = "2/1", num2 = "-2/1" Output: "0/1" Explanation: 2/1 + (-2/1) = 0/1

Approach: The given problem can be solved by converting the given rational numbers into a common denominator form, and then adding them, reducing unnecessary terms wherever possible. The steps involved in approaching the problem are:

1. Convert the given rational numbers into numerical fractions. We can do this by splitting the string by the ‘/’ character, converting the substrings into integers, and then dividing the two numbers to get the fraction.

2. Find the least common multiple (LCM) of the denominators of the two fractions. This will give us a common denominator form that we can use for both the fractions.

3. Convert both the given fractions into the common denominator form, by multiplying them by the corresponding multiplier factor, calculated as (LCM/denominator).

4. Add the two fractions, by adding the numerators and keeping the common denominator as it is.

5. Simplify the resulting fraction, if possible. This can be done by finding the greatest common divisor (GCD) of the numerator and denominator, and dividing both by it.

6. Return the simplified fraction in the required string format.

Code:

The implementation of the above approach in Python can be done as follows:

def fractionAddition(num1, num2): # Convert both the fractions to numerical form frac1 = [int(x) for x in num1.split('/')] frac2 = [int(x) for x in num2.split('/')]

# Calculate the LCM of the denominators
l = lcm(frac1[1], frac2[1])

# Convert both the fractions into the common denominator form
frac1[0] *= l//frac1[1]
frac2[0] *= l//frac2[1]
frac1[1], frac2[1] = l, l

# Add the two fractions
num = frac1[0] + frac2[0]
den = l

# Simplify the fraction, if possible
d = gcd(num, den)
num, den = num//d, den//d

# Convert the fraction back to string format
if den == 1:
    return str(num)
else:
    return str(num) + '/' + str(den)

The time complexity of the above solution is O(log10L), where L is the LCM of the two denominators, and the space complexity is O(1), as we are not using any extra data structures for storing intermediate values.

Conclusion: The above approach provides an efficient solution to the problem of computing the sum of two rational numbers, by converting them to a common denominator form and simplifying the result. The code snippet provided can be directly used to solve the problem on LeetCode platform.

1