Sum of given N fractions in reduced form

0 0 6 minutes read

Given two arrays arr1[] and arr2[] of length N which contains Numerator and Denominator of N fractions respectively, the task is to find the sum of the given N fractions in reduced form.

Examples:

Input: arr1[] = { 1, 2, 5 }, arr2[] = { 2, 1, 6 }
Output: 10/3

Input: arr1[] = { 1, 1 } arr2[] = { 2, 2 }
Output: 1/1

Approach:

Find the Least Common Multiple(LCM) of all the denominators stored in arr2[].
Change numerator of every fraction stored in arr1[] as:

Let L be the resultant LCM of all denominator(say L) and Numerator and Denominator of the fraction be N and D respectively.
Then value of each numerator must be changed to:

$New Numerator = \frac{N*L}{D}$

Find the sum of new Numerator(say sumN) formed after above step.
Divide the sumL and L by the GCD of sumL and L to get the resultant fraction in reduced form.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find  GCD of a & b
// using Euclid Lemma
int gcd(int a, int b)
{
    // Base Case
    if (b == 0) {
        return a;
    }
 
    return gcd(b, a % b);
}
 
// Function to find the LCM of all
// elements in arr[]
int findlcm(int arr[], int n)
{
    // Initialize result
    int ans = arr[0];
 
    // Iterate arr[] to find LCM
    for (int i = 1; i < n; i++) {
        ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
    }
 
    // Return the final LCM
    return ans;
}
 
// Function to find the sum of N
// fraction in reduced form
void addReduce(int n, int num[],
               int den[])
{
 
    // To store the sum of all
    // final numerators
    int final_numerator = 0;
 
    // Find the LCM of all denominator
    int final_denominator = findlcm(den, n);
 
    // Find the sum of all N
    // numerators & denominators
    for (int i = 0; i < n; i++) {
 
        // Add each fraction one by one
        final_numerator = final_numerator
                          + (num[i]) * (final_denominator
                                        / den[i]);
    }
 
    // Find GCD of final numerator and
    // denominator
    int GCD = gcd(final_numerator,
                  final_denominator);
 
    // Convert into reduced form
    // by dividing from GCD
    final_numerator /= GCD;
    final_denominator /= GCD;
 
    // Print the final fraction
    cout << final_numerator
         << "/"
         << final_denominator
         << endl;
}
 
// Driven Code
int main()
{
    // Given N
    int N = 3;
 
    // Given Numerator
    int arr1[] = { 1, 2, 5 };
 
    // Given Denominator
    int arr2[] = { 2, 1, 6 };
 
    // Function Call
    addReduce(N, arr1, arr2);
    return 0;
}

Java

// Java program for the above approach 
import java.util.*;
 
class GFG{
 
// Function to find GCD of a & b
// using Euclid Lemma
static int gcd(int a, int b)
{
     
    // Base case
    if (b == 0)
    {
        return a;
    }
 
    return gcd(b, a % b);
}
 
// Function to find the LCM of all
// elements in arr[]
static int findlcm(int arr[], int n)
{
     
    // Initialize result
    int ans = arr[0];
 
    // Iterate arr[] to find LCM
    for(int i = 1; i < n; i++) 
    {
        ans = (((arr[i] * ans)) / 
             (gcd(arr[i], ans)));
    }
 
    // Return the final LCM
    return ans;
}
 
// Function to find the sum of N
// fraction in reduced form
static void addReduce(int n, int num[],
                             int den[])
{
     
    // To store the sum of all
    // final numerators
    int final_numerator = 0;
 
    // Find the LCM of all denominator
    int final_denominator = findlcm(den, n);
 
    // Find the sum of all N
    // numerators & denominators
    for(int i = 0; i < n; i++)
    {
 
        // Add each fraction one by one
        final_numerator = final_numerator + (num[i]) *
                         (final_denominator / den[i]);
    }
 
    // Find GCD of final numerator and
    // denominator
    int GCD = gcd(final_numerator,
                  final_denominator);
 
    // Convert into reduced form
    // by dividing from GCD
    final_numerator /= GCD;
    final_denominator /= GCD;
 
    // Print the final fraction
    System.out.println(final_numerator + "/" + 
                       final_denominator);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given N
    int N = 3;
     
    // Given numerator
    int arr1[] = { 1, 2, 5 };
     
    // Given denominator
    int arr2[] = { 2, 1, 6 };
     
    // Function call
    addReduce(N, arr1, arr2);
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach 
  
# Function to find  GCD of a & b
# using Euclid Lemma
def gcd(a, b):
     
    # Base Case
    if (b == 0):
        return a
     
    return gcd(b, a % b)
 
# Function to find the LCM of all
# elements in arr[]
def findlcm(arr, n):
     
    # Initialize result
    ans = arr[0]
  
    # Iterate arr[] to find LCM
    for i in range(1, n):
        ans = (((arr[i] * ans)) //
            (gcd(arr[i], ans)))
     
    # Return the final LCM
    return ans
 
# Function to find the sum of N
# fraction in reduced form
def addReduce(n, num, den):
  
    # To store the sum of all
    # final numerators
    final_numerator = 0
  
    # Find the LCM of all denominator
    final_denominator = findlcm(den, n)
  
    # Find the sum of all N
    # numerators & denominators
    for i in range(n):
  
        # Add each fraction one by one
        final_numerator = (final_numerator +
                          (num[i]) * (final_denominator //
                           den[i]))
     
    # Find GCD of final numerator and
    # denominator
    GCD = gcd(final_numerator,
              final_denominator)
  
    # Convert into reduced form
    # by dividing from GCD
    final_numerator //= GCD
    final_denominator //= GCD
  
    # Print the final fraction
    print(final_numerator, "/",
          final_denominator)
 
# Driver Code
 
# Given N
N = 3
  
# Given Numerator
arr1 = [ 1, 2, 5 ]
  
# Given Denominator
arr2 = [ 2, 1, 6 ]
  
# Function call
addReduce(N, arr1, arr2)
 
# This code is contributed by code_hunt

C#

// C# program for the above approach 
using System;
class GFG{
  
// Function to find GCD of a & b
// using Euclid Lemma
static int gcd(int a, int b)
{
      
    // Base case
    if (b == 0)
    {
        return a;
    }
  
    return gcd(b, a % b);
}
  
// Function to find the LCM of all
// elements in arr[]
static int findlcm(int []arr, int n)
{
      
    // Initialize result
    int ans = arr[0];
  
    // Iterate arr[] to find LCM
    for(int i = 1; i < n; i++) 
    {
        ans = (((arr[i] * ans)) / 
             (gcd(arr[i], ans)));
    }
  
    // Return the final LCM
    return ans;
}
  
// Function to find the sum of N
// fraction in reduced form
static void addReduce(int n, int []num,
                             int []den)
{
      
    // To store the sum of all
    // final numerators
    int final_numerator = 0;
  
    // Find the LCM of all denominator
    int final_denominator = findlcm(den, n);
  
    // Find the sum of all N
    // numerators & denominators
    for(int i = 0; i < n; i++)
    {
  
        // Add each fraction one by one
        final_numerator = final_numerator + (num[i]) *
                         (final_denominator / den[i]);
    }
  
    // Find GCD of final numerator and
    // denominator
    int GCD = gcd(final_numerator,
                  final_denominator);
  
    // Convert into reduced form
    // by dividing from GCD
    final_numerator /= GCD;
    final_denominator /= GCD;
  
    // Print the final fraction
    Console.Write(final_numerator + "/" + 
                  final_denominator);
}
  
// Driver code
public static void Main(string[] args)
{
      
    // Given N
    int N = 3;
      
    // Given numerator
    int []arr1 = { 1, 2, 5 };
      
    // Given denominator
    int []arr2 = { 2, 1, 6 };
      
    // Function call
    addReduce(N, arr1, arr2);
}
}
  
// This code is contributed by Ritik Bansal

Javascript

<script>
 
 
// Javascript program for the above approach
 
// Function to find  GCD of a & b
// using Euclid Lemma
function gcd( a, b)
{
    // Base Case
    if (b == 0) {
        return a;
    }
 
    return gcd(b, a % b);
}
 
// Function to find the LCM of all
// elements in arr[]
function findlcm( arr,  n)
{
    // Initialize result
    var ans = arr[0];
 
    // Iterate arr[] to find LCM
    for (var i = 1; i < n; i++) {
        ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
    }
 
    // Return the final LCM
    return ans;
}
 
// Function to find the sum of N
// fraction in reduced form
function addReduce(n, num, den)
{
 
    // To store the sum of all
    // final numerators
    var final_numerator = 0;
 
    // Find the LCM of all denominator
    var final_denominator = findlcm(den, n);
 
    // Find the sum of all N
    // numerators & denominators
    for (var i = 0; i < n; i++) {
 
        // Add each fraction one by one
        final_numerator = final_numerator
                          + (num[i]) * parseInt(final_denominator
                                        / den[i]);
    }
 
    // Find GCD of final numerator and
    // denominator
    var GCD = gcd(final_numerator,
                  final_denominator);
 
    // Convert into reduced form
    // by dividing from GCD
    final_numerator = parseInt(final_numerator / GCD);
    final_denominator = parseInt(final_denominator / GCD);
 
    // Print the final fraction
    document.write( final_numerator
        + "/"
         + final_denominator
         + "<br>");
}
 
// Driven Code
// Given N
var N = 3;
 
// Given Numerator
var arr1 = [ 1, 2, 5 ];
 
// Given Denominator
var arr2 = [ 2, 1, 6 ];
 
// Function Call
addReduce(N, arr1, arr2);
 
// This code is contributed by noob2000.
</script>

Output:

10/3

Time Complexity: O(N * log(max(a, b)), where N represents the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!