Program to Add Two Fractions: C, C++ and Java with GCD

Adding two fractions a/b and c/d in code takes three steps: cross-multiply to get a raw numerator and denominator, find their GCD, then divide both by it.

The cross-multiplication formula and GCD reduction appear repeatedly in AMCAT and in-house coding sections at Indian IT companies. The Python approach is covered in the sibling article on adding fractions in Python. This article focuses on C, C++, and Java implementations, where you write the GCD function yourself or choose a standard library builtin.

The Algorithm: Three Steps

Given fractions a/b and c/d, the addition and reduction algorithm works as follows:

• Step 1: Compute the raw numerator — num = (a * d) + (c * b).
• Step 2: Compute the raw denominator — den = b * d.
• Step 3: Find g = GCD(num, den) using the Euclidean algorithm, then return num/g and den/g.

Cross-multiplication at Steps 1 and 2 always produces a valid common denominator. It is not always the least common denominator, but GCD reduction at Step 3 corrects this. The output fraction is in its simplest form regardless of whether b and d share factors.

The time complexity of the full operation is O(log(min(num, den))), driven entirely by the GCD step. The addition and division are O(1). See space and time complexity of algorithms for the general framework behind these bounds.

C Implementation

The standard C implementation writes a manual Euclidean GCD function. The loop runs until the remainder is zero:

#include <stdio.h>

int gcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

void add_fractions(int a, int b, int c, int d) {
    int num = (a * d) + (c * b);
    int den = b * d;
    int g = gcd(num, den);
    printf("%d %d\n", num / g, den / g);
}

int main() {
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    add_fractions(a, b, c, d);
    return 0;
}

Verified against all three test cases:

• Input 1 2 3 2: num = (1×2)+(3×2) = 8, den = 2×2 = 4, GCD(8, 4) = 4, output 2 1
• Input 1 3 3 9: num = (1×9)+(3×3) = 18, den = 3×9 = 27, GCD(18, 27) = 9, output 2 3
• Input 1 5 3 15: num = (1×15)+(3×5) = 30, den = 5×15 = 75, GCD(30, 75) = 15, output 2 5

All three match the expected output. The absolute-value calls in the GCD function handle the case where either fraction is negative (-3/4 + 1/4 produces a negative numerator, and the loop needs to operate on positive values to terminate correctly).

C++ Implementation

C++ offers __gcd() from the <algorithm> header (GCC, available in C++11 and later) and std::gcd() from <numeric> in C++17. Either replaces the manual loop:

#include <iostream>
#include <algorithm>   // for __gcd
using namespace std;

void add_fractions(int a, int b, int c, int d) {
    int num = (a * d) + (c * b);
    int den = b * d;
    int g = __gcd(abs(num), abs(den));
    cout << num / g << " " << den / g << endl;
}

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    add_fractions(a, b, c, d);
    return 0;
}

If your compiler targets C++17, replace __gcd(abs(num), abs(den)) with std::gcd(num, den) and include <numeric> instead of <algorithm>. The cppreference std::gcd documentation covers the full specification: std::gcd handles negative inputs by returning the GCD of their absolute values, so the abs() wrapper is unnecessary in C++17 and above.

The tradeoff: __gcd() is shorter to write and works on C++11, but it is a non-standard extension. In a competitive programming context, this rarely matters. In production code, prefer std::gcd().

Java Implementation

Java does not have a built-in GCD function in java.lang.Math, so a manual Euclidean method is the standard approach. Java’s % operator can return a negative value when the dividend is negative, so take absolute values before computing GCD:

import java.util.Scanner;

public class AddFractions {

    static long gcd(long a, long b) {
        if (a < 0) a = -a;
        if (b < 0) b = -b;
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong();
        long c = sc.nextLong(), d = sc.nextLong();
        long num = (a * d) + (c * b);
        long den = b * d;
        long g = gcd(num, den);
        System.out.println(num / g + " " + den / g);
    }
}

Note the use of long throughout. With 32-bit int inputs, the intermediate product b * d can reach about 2.1 billion and overflow silently. Using long (64-bit) covers all inputs that fit in an int with room to spare.

Edge Cases: Negative Inputs, Zero Numerator, Overflow

Three boundary conditions appear in placement tests beyond the basic examples:

Negative Fractions

For -1/3 + -1/6:

• num = (-1 × 6) + (-1 × 3) = -6 + (-3) = -9
• den = 3 × 6 = 18
• GCD of absolute values: GCD(9, 18) = 9
• Result: -9/9 and 18/9, which reduces to -1/2

The sign stays on the numerator. Always compute GCD on absolute values and then apply the division, which preserves the negative sign in the numerator correctly.

Zero Numerator

For 1/4 + (-1/4):

• num = (1 × 4) + (-1 × 4) = 4 + (-4) = 0
• den = 4 × 4 = 16
• GCD(0, 16) = 16 (because GCD(0, n) = n for all non-zero n)
• Result: 0/16 reduced by dividing both by 16, giving 0/1

No special-casing is needed. The Euclidean loop terminates immediately when a = 0, returning b as the GCD. This works correctly in all three languages.

Integer Overflow

With inputs near INT_MAX, the cross-multiplication step a * d can overflow a 32-bit signed integer:

• Use long long in C/C++ when inputs may exceed roughly 46,000 each.
• Use long in Java (already done in the Java implementation above).
• The test case format in placement tools like AMCAT typically uses inputs well below this threshold, but overflow is a valid distinguisher between correct and flawed solutions.

Digit-sum programs show a related integer-handling pattern: see digit sum programs for how to handle large input values across languages.

The __gcd() shortcut in C++ and the std::gcd() in C++17 handle the GCD step without writing a loop. Whether that tradeoff matters depends on the assessment: some in-house tests restrict library includes, making the manual Euclidean loop the only viable option. TinkerLLM (₹299) gives you a sandbox environment to run all four implementations above, test the overflow edge case by pushing inputs toward INT_MAX, and verify the GCD-vs-LCM approach side by side, which is exactly the kind of comparison placement coding rounds penalise students for skipping.