What is the best way to solve Addition of two fractions?

The optimized O(1) approach using Numbers patterns is generally preferred.

Python 기본 사항쉬움

두 분수의 덧셈

'두 분수의 덧셈' 문제에 대한 자세한 안내와 Python 구현입니다.

문제 설명

쉬움

두 개의 분수 a/b와 c/d를 나타내는 4개의 정수를 취하고 그 결과를 가장 간단한 형식(GCD로 감소)의 튜플(분자, 분모)로 반환하는 함수 add_fractions(a, b, c, d)을 작성하세요.

분수를 더하는 공식은 a/b + c/d = (a*d + b*c) / (b*d)이며, 분자와 분모를 GCD로 나누어 단순화합니다.

제약

•1 <= b, d <= 1000
•-1000 <= a, c <= 1000
•b and d are not zero

예

Example 1

Input

add_fractions(1, 2, 1, 3)

Output

(5, 6)

Explanation

1/2 + 1/3 = (1×3 + 2×1) / (2×3) = 5/6. GCD(5,6) = 1, so result is 5/6.

Example 2

Input

add_fractions(2, 4, 3, 6)

Output

(1, 1)

Explanation

2/4 + 3/6 = (2×6 + 4×3) / (4×6) = 24/24 = 1/1.

Example 3

Input

add_fractions(1, 3, 2, 3)

Output

(1, 1)

Explanation

1/3 + 2/3 = 3/3 = 1/1.

Need a Hint?

세트나 힙과 같은 Numbers 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

Numbers 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(1)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def add_fractions_opt(n1, d1, n2, d2):
    import math
    num = n1 * d2 + n2 * d1
    den = d1 * d2
    common = math.gcd(num, den)
    return f"{num // common}/{den // common}"

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def add_fractions_brute(n1, d1, n2, d2):
    def gcd(a, b):
        while b: a, b = b, a % b
        return a
    num = n1 * d2 + n2 * d1
    den = d1 * d2
    common = gcd(num, den)
    return f"{num // common}/{den // common}"