What is the time complexity of Fraction Addition and Subtraction?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Fraction Addition and Subtraction?

This problem uses Math, String, Simulation. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Fraction Addition and Subtraction?

Insight 1: The core idea is to iterate through the fractions, adding or subtracting each one from the current sum. This requires parsing each fraction into its numerator and denominator. Insight 2: To add or subtract fractions, we need a common denominator. The formula a/b + c/d = (a*d + b*c) / (b*d) is crucial for adding two fractions.

Which companies ask LeetCode 592. Fraction Addition and Subtraction in interviews?

This problem is frequently asked at Goldman Sachs, IXL, Zopsmart.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Fraction Addition and Subtraction - LeetCode 592 Solution

Fraction Addition and Subtraction - Complete Solution Guide

Fraction Addition and Subtraction is LeetCode problem 592, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a string expression representing an expression of fraction addition and subtraction, return the calculation result in string format. The final result should be an irreducible fraction . If your final result is an integer, change it to the format of a fraction that has a denominator 1 . So in this case, 2 should be converted to 2/1 . Example 1: Input: expression = "-1/2+1/2" Output: "0/1" Example 2: Input: expression = "-1/2+1/2+1/3" Output: "1/3" Example 3: Input: expression = "1/3-1/2" Ou

Detailed Explanation

The problem asks us to take a string representing an expression of fraction additions and subtractions (e.g., "-1/2+1/2+1/3") and return the result of the expression as a single irreducible fraction string (e.g., "1/3"). The input fractions are guaranteed to be irreducible and have numerators and denominators between 1 and 10. The final output should also be in the form of an irreducible fraction. If the result is an integer, it should be formatted as 'X/1'.

Solution Approach

The provided solutions iterate through the input string, extracting each fraction, and perform fraction addition or subtraction sequentially. For each fraction: the numerator and denominator are parsed from the string. Then, the current fraction is added to the accumulated sum using the formula a/b + c/d = (ad + bc) / bd. After each addition, the resulting fraction is simplified by dividing both the numerator and denominator by their greatest common divisor (GCD). Finally, the result is formatted as a string "numerator/denominator".

Step-by-Step Algorithm

Step 1: Parse the input string to identify and extract all fractions as strings.
Step 2: Initialize the `numerator_sum` to 0 and `denominator_sum` to 1 (representing 0/1 as the initial sum).
Step 3: Iterate through the extracted fractions.
Step 4: For each fraction, split the string into its `numerator` and `denominator` components.
Step 5: Convert the `numerator` and `denominator` strings to integers.
Step 6: Calculate the new `numerator_sum` and `denominator_sum` using the formula: `numerator_sum = numerator_sum * denominator + denominator_sum * numerator` and `denominator_sum = denominator_sum * denominator`.
Step 7: Calculate the greatest common divisor (GCD) of the absolute values of `numerator_sum` and `denominator_sum`.
Step 8: Divide both `numerator_sum` and `denominator_sum` by the GCD to simplify the fraction.
Step 9: After iterating through all fractions, format the final `numerator_sum` and `denominator_sum` into a string of the form "numerator/denominator" and return it.

Key Insights

Insight 1: The core idea is to iterate through the fractions, adding or subtracting each one from the current sum. This requires parsing each fraction into its numerator and denominator.
Insight 2: To add or subtract fractions, we need a common denominator. The formula a/b + c/d = (a*d + b*c) / (b*d) is crucial for adding two fractions.
Insight 3: Simplifying the fraction after each addition or subtraction by finding the greatest common divisor (GCD) prevents integer overflow and keeps numbers manageable. The final result must be irreducible.
Insight 4: Proper parsing of the input string to extract numerators and denominators correctly, handling the signs (+ or -), is critical.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Math, String, Simulation.

Companies

Asked at: Goldman Sachs, IXL, Zopsmart.

Fraction Addition and Subtraction | LeetCode 592

Medium

Math String Simulation

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    public String fractionAddition(String expression) {
        // The regex finds all fraction terms, e.g., "-1/2+1/3" -> ['-1/2', '+1/3'].
        // The pattern '[+-]?\d+/\d+' matches an optional sign, digits for the numerator,
        // a slash, and digits for the denominator.
        Pattern pattern = Pattern.compile("[+-]?\\d+/\\d+");
        Matcher matcher = pattern.matcher(expression);
        
        // Store the fractions in a list
        java.util.ArrayList<String> fractions = new java.util.ArrayList<>();
        while (matcher.find()) {
            fractions.add(matcher.group());
        }

        // Initialize the total sum as 0/1.
        int numerator_sum = 0;
        int denominator_sum = 1;

        for (String frac : fractions) {
            // Parse the current fraction string into its numerator and denominator.
            String[] parts = frac.split("/");
            int num = Integer.parseInt(parts[0]);
            int den = Integer.parseInt(parts[1]);

            // Add the current fraction (num/den) to the running sum (numerator_sum/denominator_sum).
            // The formula for a/b + c/d is (a*d + b*c) / (b*d).
            numerator_sum = numerator_sum * den + denominator_sum * num;
            denominator_sum = denominator_sum * den;

            // Simplify the resulting fraction to keep the numbers manageable and to
            // prepare for the next addition.
            int common_divisor = gcd(numerator_sum, denominator_sum);

            numerator_sum /= common_divisor;
            denominator_sum /= common_divisor;
        }

        // Format the final irreducible fraction into the required string format.
        return numerator_sum + "/" + denominator_sum;
    }

    private int gcd(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 592: Fraction Addition and Subtraction - Detailed explanation and solution approaches.

Topics

Math String Simulation

Companies

Goldman SachsIXLZopsmart

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:592

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Parse the input string to identify and extract all fractions as strings.
2
Step 2: Initialize the `numerator_sum` to 0 and `denominator_sum` to 1 (representing 0/1 as the initial sum).
3
Step 3: Iterate through the extracted fractions.
4
Step 4: For each fraction, split the string into its `numerator` and `denominator` components.
5
Step 5: Convert the `numerator` and `denominator` strings to integers.
6
Step 6: Calculate the new `numerator_sum` and `denominator_sum` using the formula: `numerator_sum = numerator_sum * denominator + denominator_sum * numerator` and `denominator_sum = denominator_sum * denominator`.
7
Step 7: Calculate the greatest common divisor (GCD) of the absolute values of `numerator_sum` and `denominator_sum`.
8
Step 8: Divide both `numerator_sum` and `denominator_sum` by the GCD to simplify the fraction.
9
Step 9: After iterating through all fractions, format the final `numerator_sum` and `denominator_sum` into a string of the form "numerator/denominator" and return it.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is dominated by the iteration through the fractions. The space complexity is mainly due to storing the individual fractions in an array or list. The simplification step with GCD is relatively constant due to the constrained size of the numerator and denominator.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a stack-based approach

Instead of directly iterating and adding, you can use a stack to keep track of the intermediate fractions. This might be useful if the expression had more complex operations like parentheses.

Time: O(n)Space: O(n)

Trade-offs: Stack-based approach can handle more complex expressions but adds overhead in this case.

✨

Key Insights

1Insight 1: The core idea is to iterate through the fractions, adding or subtracting each one from the current sum. This requires parsing each fraction into its numerator and denominator.
2Insight 2: To add or subtract fractions, we need a common denominator. The formula a/b + c/d = (a*d + b*c) / (b*d) is crucial for adding two fractions.
3Insight 3: Simplifying the fraction after each addition or subtraction by finding the greatest common divisor (GCD) prevents integer overflow and keeps numbers manageable. The final result must be irreducible.
4Insight 4: Proper parsing of the input string to extract numerators and denominators correctly, handling the signs (+ or -), is critical.

📚

Key Terms Explained

For Students

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Input expression with only one fraction, such as "1/2". The algorithm should correctly parse and return this fraction without any additions.
Edge case 2: Input expression that results in zero, such as "-1/2+1/2". The algorithm should simplify the result to "0/1".
Edge case 3: Input expression with only additions or only subtractions. The algorithm should handle both correctly.
Edge case 4: Fractions where the numerator or denominator is negative. The algorithm correctly handles negative numerators via the sign in the input string. Note that negative denominators should resolve into a negative numerator, and the denominator must always be positive by convention when simplifying.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to simplify the fraction after each addition or subtraction. This can lead to large numerator and denominator values and potentially integer overflow.

✗Common mistake 2: Incorrectly parsing the input string, especially when handling the '+' and '-' signs. It is important to account for the leading sign and signs between fractions.

✗Common mistake 3: Not handling the case where the final result is zero correctly. The result should be "0/1".

✗Common mistake 4: Not handling the case where the result has a negative numerator and positive denominator.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Financial calculations involving fractions of assets or investments.

🏦Real-world scenario 2: Scientific simulations where quantities are represented as fractions and need to be combined.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 23, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Fraction Addition and Subtraction"?

For this medium-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?