Evaluate fraction sum and reduce it in python

View Discussion

Improve Article

Save Article

View Discussion

Improve Article

Save Article

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:
 

• 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++

#include

using namespace std;

int gcd(int a, int b)

{

    if (b == 0) {

        return a;

    }

    return gcd(b, a % b);

}

int findlcm(int arr[], int n)

{

    int ans = arr[0];

    for (int i = 1; i < n; i++) {

        ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));

    }

    return ans;

}

void addReduce(int n, int num[],

               int den[])

{

    int final_numerator = 0;

    int final_denominator = findlcm(den, n);

    for (int i = 0; i < n; i++) {

        final_numerator = final_numerator

                          + (num[i]) * (final_denominator

                                        / den[i]);

    }

    int GCD = gcd(final_numerator,

                  final_denominator);

    final_numerator /= GCD;

    final_denominator /= GCD;

    cout << final_numerator

         << "/"

         << final_denominator

         << endl;

}

int main()

{

    int N = 3;

    int arr1[] = { 1, 2, 5 };

    int arr2[] = { 2, 1, 6 };

    addReduce(N, arr1, arr2);

    return 0;

}

Java

import java.util.*;

class GFG{

static int gcd(int a, int b)

{

    if (b == 0)

    {

        return a;

    }

    return gcd(b, a % b);

}

static int findlcm(int arr[], int n)

{

    int ans = arr[0];

    for(int i = 1; i < n; i++)

    {

        ans = (((arr[i] * ans)) /

             (gcd(arr[i], ans)));

    }

    return ans;

}

static void addReduce(int n, int num[],

                             int den[])

{

    int final_numerator = 0;

    int final_denominator = findlcm(den, n);

    for(int i = 0; i < n; i++)

    {

        final_numerator = final_numerator + (num[i]) *

                         (final_denominator / den[i]);

    }

    int GCD = gcd(final_numerator,

                  final_denominator);

    final_numerator /= GCD;

    final_denominator /= GCD;

    System.out.println(final_numerator + "/" +

                       final_denominator);

}

public static void main(String[] args)

{

    int N = 3;

    int arr1[] = { 1, 2, 5 };

    int arr2[] = { 2, 1, 6 };

    addReduce(N, arr1, arr2);

}

}

Python3

def gcd(a, b):

    if (b == 0):

        return a

    return gcd(b, a % b)

def findlcm(arr, n):

    ans = arr[0]

    for i in range(1, n):

        ans = (((arr[i] * ans)) //

            (gcd(arr[i], ans)))

    return ans

def addReduce(n, num, den):

    final_numerator = 0

    final_denominator = findlcm(den, n)

    for i in range(n):

        final_numerator = (final_numerator +

                          (num[i]) * (final_denominator //

                           den[i]))

    GCD = gcd(final_numerator,

              final_denominator)

    final_numerator //= GCD

    final_denominator //= GCD

    print(final_numerator, "/",

          final_denominator)

N = 3

arr1 = [ 1, 2, 5 ]

arr2 = [ 2, 1, 6 ]

addReduce(N, arr1, arr2)

C#

using System;

class GFG{

static int gcd(int a, int b)

{

    if (b == 0)

    {

        return a;

    }

    return gcd(b, a % b);

}

static int findlcm(int []arr, int n)

{

    int ans = arr[0];

    for(int i = 1; i < n; i++)

    {

        ans = (((arr[i] * ans)) /

             (gcd(arr[i], ans)));

    }

    return ans;

}

static void addReduce(int n, int []num,

                             int []den)

{

    int final_numerator = 0;

    int final_denominator = findlcm(den, n);

    for(int i = 0; i < n; i++)

    {

        final_numerator = final_numerator + (num[i]) *

                         (final_denominator / den[i]);

    }

    int GCD = gcd(final_numerator,

                  final_denominator);

    final_numerator /= GCD;

    final_denominator /= GCD;

    Console.Write(final_numerator + "/" +

                  final_denominator);

}

public static void Main(string[] args)

{

    int N = 3;

    int []arr1 = { 1, 2, 5 };

    int []arr2 = { 2, 1, 6 };

    addReduce(N, arr1, arr2);

}

}

Javascript

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.