HCF of an array of fractions (or rational numbers)

HCF or the Highest common factor of two or more numbers refers to the highest number which divides them.

A rational number is the quotient p/q of two numbers such that q is not equal to 0.

Problem Statement

Given an array with fractional numbers, find the HCF of the numbers.

Example 1

Input

[{4, 5}, {10, 12}, {24, 16}, {22, 13}] 

Output

{2, 3120} 

Explanation

The fractional numbers given are: 4/5, 10/12, 24/16 and 22/13

2/3120 is the largest number that divides all of them.

Example 2

Input

[{18, 20}, {15, 12}, {27, 12}, {20, 6}] 

Output

{3, 1400} 

Explanation

The fractional numbers given are: 18/20, 15/12, 27/12 and 20/6

1/60 is the largest number that divides all of them.

Approach

To find the HCF of a fractional number, do the following steps ?

• Compute the HCF of the numerators.

• Compute the LCM of the denominators.

• Compute HCF/LCM.

• If possible, reduce the fraction to the lowest fraction.

Let's break the above approach into two parts ?

Finding the HCF of numerators

For finding the HCF of two numbers, the Euclidean approach is used.

The algorithm uses the following facts ?

• The HCF of two numbers doesn't change if we subtract the smaller number from the larger one. Thus, if we keep subtracting the smaller number from the larger of the two, we end up with the HCF.

• Instead of subtraction, we can use division. If we divide the smaller number, the algorithm stops when the remainder becomes 0.

C++ Function for Finding HCF of two numbers

//Function to find HCF of two numbers int HCF(int a, int b) { if (a % b == 0) return b; else return (HCF(b, a % b)); } 

Now, we can iteratively find the HCF of the numerators of the entire array (more than two numbers).

//Function to find HCF of the numerator series int findHcf(vector<pair<int,int>>v) { int hcf = v[0].first; for (int i = 1; i < v.size(); i++) hcf = HCF(hcf, v[i].first); // return hcf of the numerators return (hcf); } 

Finding the LCM of the denominators

To find the LCM of two numbers a and b, we can use the following formula ?

LCM(a,b) * HCF (a,b) = a*b Hence, LCM(a,b) = (a*b) / HCF(a,b) 

Now, we can iteratively find the LCM of the numerators of the entire array (more than two numbers).

C++ Function for finding the LCM of the denominators

//Function to find lcm of the denominator series int findLcm(vector<pair<int,int>>v) { // ans contains LCM of arr[0][1], ..arr[i][1] int lcm = v[0].second; for (int i = 1; i < v.size(); i++) lcm = (((v[i].second * lcm)) / (HCF(v[i].second, lcm))); // return lcm of the denominator return (lcm); } 

• STEP 1 ? Initialize a vector of pairs: vector<pair<int,int>>vec

• STEP 2 ? Take the input of fractions in vec

• STEP 3 ? ans -> find_hcf_of_fraction(vec)

• STEP 4 ? Print ans

Pseudocode

Function find_hcf_of_fraction(vec): HCF_of_num -> findHCF(vec)	LCM_of_denom -> findLCM(vec)	Initialize vector ans: vectorans;	ans -> [Hcf_of_num, Lcm_of_num]	For i = ans[0]/2 to 2:	if (ans[1] % i == 0) and (ans[0] % i == 0):	ans[1] -> ans[1]/i	ans[0] -> ans[0]/i	return ans Function find_HCF(vec):	hcf -> vec[0].first	For i=0 to vec.size()-1:	hcf -> HCF(ans, vec[i].first)	return ans Function HCF(a,b):	if a%b->0:	return a	else:	return HCF(b , a%b) Function findLCM(vec):	lcm -> vec[0].second	For i=0 to vec.size()-1:	lcm-> (lcm* vec[i].second) / (hcf (vec[i].second, lcm))	return lcm 

Example (C++ program)

Below is a CPP program to find the HCF of an array of rational numbers (fractions).

#include <bits/stdc++.h> using namespace std; //Function to find HCF of two numbers int HCF(int a, int b){ if (a % b == 0) return b; else return (HCF(b, a % b)); } //Function to find HCF of the numerator series int findHcf(vector<pair<int,int>>v){ int hcf = v[0].first; for (int i = 1; i < v.size(); i++) hcf = HCF(hcf, v[i].first); // return hcf of the numerators return (hcf); } //Function to find lcm of the denominator series int findLcm(vector<pair<int,int>>v){ // ans contains LCM of arr[0][1], ..arr[i][1] int lcm = v[0].second; for (int i = 1; i < v.size(); i++) lcm = (((v[i].second * lcm)) / (HCF(v[i].second, lcm))); // return lcm of the denominator return (lcm); } //Function to get the answer vector<int> find_hcf_of_fraction(vector<pair<int,int>>v){ //HCF of the numerator series int hcf_of_num = findHcf(v); // lcm of the denominator series int lcm_of_deno = findLcm(v); vector<int>ans(2); ans[0] = hcf_of_num; ans[1] = lcm_of_deno; for (int i = ans[0] / 2; i > 1; i--) { if ((ans[1] % i == 0) && (ans[0] % i == 0)) { ans[1] /= i; ans[0] /= i; } } // return answer return (ans); } //main code int main(){ int size = 4; vector<pair<int,int>>vec; //Inserting the fractions in the vector vec.push_back({4,5}); vec.push_back({10,12}); vec.push_back({24,16}); vec.push_back({22,13}); //Function call to calculate the HCF of the fractions vector<int>ans; ans = find_hcf_of_fraction(vec); //Print the answer cout << "HCF of given array of fractions: "; cout << "{" << ans[0] << ", " << ans[1] << "}"<< endl; return 0; } 

Output

For the input - [{4, 5}, {10, 12}, {24, 16}, {22, 13}], the above C++ program will produce the following output ?

HCF of given array of fractions: {2, 3120} 

Conclusion

This article discusses the problem of finding the HCF of fractional numbers. The things which were covered in the article included the approach, the pseudocode and the C++ Program.