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/3Input: 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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find GCD of a & b// using Euclid Lemmaint 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 formvoid 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 Codeint 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 Lemmastatic 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 formstatic 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 codepublic 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 Lemmadef 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 formdef 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 NN = 3 # Given Numeratorarr1 = [ 1, 2, 5 ] # Given Denominatorarr2 = [ 2, 1, 6 ] # Function calladdReduce(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 Lemmastatic 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 formstatic 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 codepublic 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 Lemmafunction 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 formfunction 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 Nvar N = 3;// Given Numeratorvar arr1 = [ 1, 2, 5 ];// Given Denominatorvar arr2 = [ 2, 1, 6 ];// Function CalladdReduce(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
