Given a fraction series. Find the H.C.F of a given fraction series.
Examples:
Input : [{2, 5}, {8, 9}, {16, 81}, {10, 27}]
Output : 2, 405
Explanation : 2/405 is the largest number that
divides all 2/5, 8/9, 16/81 and 10/27.
Input : [{9, 10}, {12, 25}, {18, 35}, {21, 40}]
Output : 3, 1400
Approach:
Find the H.C.F of numerators. Find the L.C.M of denominators. Calculate fraction of H.C.F/L.C.M. Reduce the fraction to Lowest Fraction.
Implementation:
C++
// CPP program to find HCF of array of // rational numbers (fractions).#include <iostream>using namespace std;// hcf of two numberint gcd(int a, int b){ if (a % b == 0) return b; else return (gcd(b, a % b));}// find hcf of numerator seriesint findHcf(int** arr, int size){ int ans = arr[0][0]; for (int i = 1; i < size; i++) ans = gcd(ans, arr[i][0]); // return hcf of numerator return (ans);}// find lcm of denominator seriesint findLcm(int** arr, int size){ // ans contains LCM of arr[0][1], ..arr[i][1] int ans = arr[0][1]; for (int i = 1; i < size; i++) ans = (((arr[i][1] * ans)) / (gcd(arr[i][1], ans))); // return lcm of denominator return (ans);}// Core Functionint* hcfOfFraction(int** arr, int size){ // found hcf of numerator int hcf_of_num = findHcf(arr, size); // found lcm of denominator int lcm_of_deno = findLcm(arr, size); int* result = new int[2]; result[0] = hcf_of_num; result[1] = lcm_of_deno; for (int i = result[0] / 2; i > 1; i--) { if ((result[1] % i == 0) && (result[0] % i == 0)) { result[1] /= i; result[0] /= i; } } // return result return (result);}// Main functionint main(){ int size = 4; int** arr = new int*[size]; // Initialize the every row // with size 2 (1 for numerator // and 2 for denominator) for (int i = 0; i < size; i++) arr[i] = new int[2]; arr[0][0] = 9; arr[0][1] = 10; arr[1][0] = 12; arr[1][1] = 25; arr[2][0] = 18; arr[2][1] = 35; arr[3][0] = 21; arr[3][1] = 40; // function for calculate the result int* result = hcfOfFraction(arr, size); // print the result cout << result[0] << ", " << result[1] << endl; return 0;} |
Java
// Java program to find HCF of array of // rational numbers (fractions).class GFG {// hcf of two numberstatic int gcd(int a, int b){ if (a % b == 0) return b; else return (gcd(b, a % b));}// find hcf of numerator seriesstatic int findHcf(int [][]arr, int size){ int ans = arr[0][0]; for (int i = 1; i < size; i++) ans = gcd(ans, arr[i][0]); // return hcf of numerator return (ans);}// find lcm of denominator seriesstatic int findLcm(int[][] arr, int size){ // ans contains LCM of arr[0][1], ..arr[i][1] int ans = arr[0][1]; for (int i = 1; i < size; i++) ans = (((arr[i][1] * ans)) / (gcd(arr[i][1], ans))); // return lcm of denominator return (ans);}// Core Functionstatic int[] hcfOfFraction(int[][] arr, int size){ // found hcf of numerator int hcf_of_num = findHcf(arr, size); // found lcm of denominator int lcm_of_deno = findLcm(arr, size); int[] result = new int[2]; result[0] = hcf_of_num; result[1] = lcm_of_deno; for (int i = result[0] / 2; i > 1; i--) { if ((result[1] % i == 0) && (result[0] % i == 0)) { result[1] /= i; result[0] /= i; } } // return result return (result);}// Driver codepublic static void main(String[] args){ int size = 4; int[][] arr = new int[size][size]; // Initialize the every row // with size 2 (1 for numerator // and 2 for denominator) for (int i = 0; i < size; i++) arr[i] = new int[2]; arr[0][0] = 9; arr[0][1] = 10; arr[1][0] = 12; arr[1][1] = 25; arr[2][0] = 18; arr[2][1] = 35; arr[3][0] = 21; arr[3][1] = 40; // function for calculate the result int[] result = hcfOfFraction(arr, size); // print the result System.out.println(result[0] + ", " + result[1]); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python 3 program to find HCF of array of from math import gcd# find hcf of numerator seriesdef findHcf(arr, size): ans = arr[0][0] for i in range(1, size, 1): ans = gcd(ans, arr[i][0]) # return hcf of numerator return (ans)# find lcm of denominator seriesdef findLcm(arr, size): # ans contains LCM of arr[0][1], ..arr[i][1] ans = arr[0][1] for i in range(1, size, 1): ans = int((((arr[i][1] * ans)) / (gcd(arr[i][1], ans)))) # return lcm of denominator return (ans)# Core Functiondef hcfOfFraction(arr, size): # found hcf of numerator hcf_of_num = findHcf(arr, size) # found lcm of denominator lcm_of_deno = findLcm(arr, size) result = [0 for i in range(2)] result[0] = hcf_of_num result[1] = lcm_of_deno i = int(result[0] / 2) while(i > 1): if ((result[1] % i == 0) and (result[0] % i == 0)): result[1] = int(result[1] / i) result[0] = (result[0] / i) # return result return (result)# Driver Codeif __name__ == '__main__': size = 4 arr = [0 for i in range(size)] # Initialize the every row # with size 2 (1 for numerator # and 2 for denominator) for i in range(size): arr[i] = [0 for i in range(2)] arr[0][0] = 9 arr[0][1] = 10 arr[1][0] = 12 arr[1][1] = 25 arr[2][0] = 18 arr[2][1] = 35 arr[3][0] = 21 arr[3][1] = 40 # function for calculate the result result = hcfOfFraction(arr, size) # print the result print(result[0], ",", result[1]) # This code is contributed by# Surendra_Gangwar |
C#
// C# program to find HCF of array of // rational numbers (fractions).using System;class GFG {// hcf of two numberstatic int gcd(int a, int b){ if (a % b == 0) return b; else return (gcd(b, a % b));}// find hcf of numerator seriesstatic int findHcf(int [,]arr, int size){ int ans = arr[0, 0]; for (int i = 1; i < size; i++) ans = gcd(ans, arr[i, 0]); // return hcf of numerator return (ans);}// find lcm of denominator seriesstatic int findLcm(int[,] arr, int size){ // ans contains LCM of arr[0,1], ..arr[i,1] int ans = arr[0,1]; for (int i = 1; i < size; i++) ans = (((arr[i, 1] * ans)) / (gcd(arr[i, 1], ans))); // return lcm of denominator return (ans);}// Core Functionstatic int[] hcfOfFraction(int[,] arr, int size){ // found hcf of numerator int hcf_of_num = findHcf(arr, size); // found lcm of denominator int lcm_of_deno = findLcm(arr, size); int[] result = new int[2]; result[0] = hcf_of_num; result[1] = lcm_of_deno; for (int i = result[0] / 2; i > 1; i--) { if ((result[1] % i == 0) && (result[0] % i == 0)) { result[1] /= i; result[0] /= i; } } // return result return (result);}// Driver codepublic static void Main(String[] args){ int size = 4; int[,] arr = new int[size, size]; // Initialize the every row // with size 2 (1 for numerator // and 2 for denominator) arr[0, 0] = 9; arr[0, 1] = 10; arr[1, 0] = 12; arr[1, 1] = 25; arr[2, 0] = 18; arr[2, 1] = 35; arr[3, 0] = 21; arr[3, 1] = 40; // function for calculate the result int[] result = hcfOfFraction(arr, size); // print the result Console.WriteLine(result[0] + ", " + result[1]); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find HCF of array of // rational numbers (fractions).// hcf of two numberfunction gcd(a,b){ if (a % b == 0) return b; else return (gcd(b, a % b));}// find hcf of numerator seriesfunction findHcf(arr,size){ let ans = arr[0][0]; for (let i = 1; i < size; i++) ans = gcd(ans, arr[i][0]); // return hcf of numerator return (ans);}// find lcm of denominator seriesfunction findLcm(arr,size){ // ans contains LCM of arr[0][1], ..arr[i][1] let ans = arr[0][1]; for (let i = 1; i < size; i++) ans = Math.floor(((arr[i][1] * ans)) / (gcd(arr[i][1], ans))); // return lcm of denominator return (ans);}// Core Functionfunction hcfOfFraction(arr,size){ // found hcf of numerator let hcf_of_num = findHcf(arr, size); // found lcm of denominator let lcm_of_deno = findLcm(arr, size); let result = new Array(2); result[0] = hcf_of_num; result[1] = lcm_of_deno; for (let i = result[0] / 2; i > 1; i--) { if ((result[1] % i == 0) && (result[0] % i == 0)) { result[1] /= i; result[0] /= i; } } // return result return (result);}// Driver codelet size = 4;let arr = new Array(size);// Initialize the every row// with size 2 (1 for numerator// and 2 for denominator)for (let i = 0; i < size; i++) arr[i] = new Array(2);arr[0][0] = 9;arr[0][1] = 10;arr[1][0] = 12;arr[1][1] = 25;arr[2][0] = 18;arr[2][1] = 35;arr[3][0] = 21;arr[3][1] = 40;// function for calculate the resultlet result = hcfOfFraction(arr, size);// print the resultdocument.write(result[0] + ", " + result[1]+"<br>");// This code is contributed by rag2127</script> |
Output
3, 1400
Time Complexity: O(n log(a)) , where a is the maximum element in array
Auxiliary Space: O(log(a)), where a is the maximum element in array
Please suggest if someone has a better solution which is more efficient in terms of space and time.
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!
