Add Two Fraction

44
0

Given two strings fraction1 and fraction2 in the forms "a/b" and "c/d", where a, b, c, and d are positive integers.

Return their sum in simplest form as a string "x/y".

A fraction is in simplest form when its numerator and denominator have no common divisor greater than 1.

Example 1

Input: fraction1 = "7/30", fraction2 = "11/42"

Output:"52/105"

Explanation: The least common denominator is 210. The two fractions become 49/210 and 55/210, giving 104/210. Dividing both parts by 2 gives 52/105.

Example 1

Input:fraction1 = "5/12", fraction2 = "7/12"

Output: "1/1"

Explanation: Both fractions already have denominator 12, so their sum is 12/12. Reducing the sum gives 1/1.

Approach

The denominator tells how large each fractional part is. Numerators can be added once both fractions describe parts of the same size. Multiplying a numerator and its denominator by the same factor preserves the value, so both fractions can be rewritten with a common denominator.

When both fractions are scaled directly from their input forms, the least common multiple of b and d is the smallest denominator they can share. If g is their greatest common divisor (GCD), the least common multiple is b × (d / g). The division removes the factor shared by both denominators from their product. The first numerator is scaled by d / g and the second by b / g.

The sum may still have a common factor in its numerator and denominator. Euclid’s algorithm relies on the fact that the dividend and divisor have the same common divisors as the divisor and remainder. This follows from dividend = quotient × divisor + remainder. Dividing both parts of the sum by their GCD preserves its value and leaves a fraction in simplest form.

Algorithm

  • Split both strings at / and read each numerator and denominator as an exact integer.

  • Find the GCD of the two denominators. In Euclid’s algorithm, replace each pair with its second number and the remainder until the second number is 0. The first number is then the GCD.

  • Divide each denominator by that GCD to get the scale factor for the other fraction. Multiply the first denominator by its scale factor to get the common denominator.

  • Multiply each numerator by its fraction’s scale factor, then add the scaled numerators.

  • Find the GCD of the resulting numerator and denominator, then divide both by it.

  • Return the reduced fraction as "x/y".

Dry Run

Add Two Fraction

Add Two Fraction


Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to compute gcd
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
// Function to add two fractions
string addFractions(string frac1, string frac2) {
// Parse first fraction
int num1, den1;
sscanf(frac1.c_str(), "%d/%d", &num1, &den1);
// Parse second fraction
int num2, den2;
sscanf(frac2.c_str(), "%d/%d", &num2, &den2);
// Find lcm of denominators
int lcm = den1 * den2 / gcd(den1, den2);
// Adjust numerators
int numerator = num1 * (lcm / den1) + num2 * (lcm / den2);
// Simplify result
int g = gcd(abs(numerator), lcm);
numerator /= g;
lcm /= g;
// Return result
return to_string(numerator) + "/" + to_string(lcm);
}
};
int main() {
Solution s;
string frac1 = "1/2", frac2 = "3/4";
cout << s.addFractions(frac1, frac2) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N²) using classical digit arithmetic, where N is the total number of input characters. Every intermediate integer has O(N) digits, and decimal conversion, fraction arithmetic, and the two Euclidean GCD computations each take at most quadratic time in this model.

Space Complexity: O(N) auxiliary space for the parsed strings and a constant number of integers with O(N) digits each. The returned string also uses O(N) space.

Interview follow-up Questions

Yes. The sum is (a × d + c × b) / (b × d), and a final GCD reduction gives the same result. When the denominators share factors, using their least common multiple keeps the intermediate numerator and denominator smaller.

MathsStringTCS NQT

Read Similar Blogs

Comments0