Given an array of rational numbers, the task is to find the LCM of these numbers.
Examples:
Input : vect[] = {2/7, 3/14, 5/3}
Output : 30/1
Input : vect[] = {3/14, 5/3}
Output : 15/1
Input : vect[] = {3/4, 3/2}
Output : 3/2
First find the lcm of all numerator of rational number then find the gcd of all the denominator of rational number then divide lcm of all numerator/ gcd of all the denominator this the lcm of rational number’s.
Formula:-
LCM of all the numerator of Rational number's
lcm = -----------------------------------------------
GCD of all the denominator of Rational number's
Implementation:
C++
// CPP program to find LCM of given array#include <bits/stdc++.h>using namespace std;// get lcm of two numbersint LCM(int a, int b){ return (a * b) / (__gcd(a, b));}// Finds LCM of numeratorsint lcmOfNumerator(vector<pair<int, int> > vect){ // calculate the lcm of all numerators int lcm = vect[0].first; for (int i = 1; i < vect.size(); i++) lcm = LCM(vect[i].first, lcm); // return all numerator lcm return lcm;}// Get GCD of all the denominatorsint gcdOfDemoninators(vector<pair<int, int> > vect){ // calculate the gcd of all the denominators int gcd = vect[0].second; for (int i = 1; i < vect.size(); i++) gcd = __gcd(vect[i].second, gcd); // return all denominator gcd return gcd;}// find lcm of all the rational numbervoid lcmOfRationals(vector<pair<int, int> > vect){ // return the LCM of all numerator/ GCD of all // denominator cout << lcmOfNumerator(vect) << "/" << gcdOfDemoninators(vect);}// Driver codeint main(){ vector<pair<int, int> > vect; // give rational number 2/7, 3/14, 5/3 // make pair as a numerator and denominator vect.push_back(make_pair(2, 7)); vect.push_back(make_pair(3, 14)); vect.push_back(make_pair(5, 3)); lcmOfRationals(vect); return 0;} |
Java
// JAVA program to find LCM of given arrayimport java.util.*;class GFG{ static class pair{ int first, second; public pair(int first, int second) { this.first = first; this.second = second; } }// get lcm of two numbersstatic int LCM(int a, int b){ return (a * b) / (__gcd(a, b));}static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); }// Finds LCM of numeratorsstatic int lcmOfNumerator(Vector<pair> vect){ // calculate the lcm of all numerators int lcm = vect.get(0).first; for (int i = 1; i < vect.size(); i++) lcm = LCM(vect.get(i).first, lcm); // return all numerator lcm return lcm;}// Get GCD of all the denominatorsstatic int gcdOfDemoninators(Vector<pair> vect){ // calculate the gcd of all the denominators int gcd = vect.get(0).second; for (int i = 1; i < vect.size(); i++) gcd = __gcd(vect.get(i).second, gcd); // return all denominator gcd return gcd;}// find lcm of all the rational numberstatic void lcmOfRationals(Vector<pair> vect){ // return the LCM of all numerator/ GCD of all // denominator System.out.print(lcmOfNumerator(vect)+ "/" + gcdOfDemoninators(vect));}// Driver codepublic static void main(String[] args){ Vector<pair> vect = new Vector<pair>(); // give rational number 2/7, 3/14, 5/3 // make pair as a numerator and denominator vect.add(new pair(2, 7)); vect.add(new pair(3, 14)); vect.add(new pair(5, 3)); lcmOfRationals(vect);}}// This code is contributed by Rajput-Ji |
Python
# Python program to find LCM of given array import math# get lcm of two numbers def LCM(a, b): return (a * b) // (math.gcd(a, b)) # Finds LCM of numerators def lcmOfNumerator(vect): # calculate the lcm of all numerators lcm = vect[0][0] for i in range(1, len(vect)): lcm = LCM(vect[i][0], lcm) # return all numerator lcm return lcm # Get GCD of all the denominators def gcdOfDemoninators(vect): # calculate the gcd of all the denominators gcd = vect[0][1] for i in range(1, len(vect)): gcd = math.gcd(vect[i][1], gcd) # return all denominator gcd return gcd # find lcm of all the rational number def lcmOfRationals(vect): # return the LCM of all numerator/ GCD of all # denominator print(lcmOfNumerator(vect), "/", gcdOfDemoninators(vect), sep = "")# Driver code vect = []# give rational number 2/7, 3/14, 5/3 # make pair as a numerator and denominator vect.append((2, 7)) vect.append((3, 14)) vect.append((5, 3)) lcmOfRationals(vect) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to find LCM of given arrayusing System;using System.Collections.Generic;class GFG{ class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } }// get lcm of two numbersstatic int LCM(int a, int b){ return (a * b) / (__gcd(a, b));}static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); }// Finds LCM of numeratorsstatic int lcmOfNumerator(List<pair> vect){ // calculate the lcm of all numerators int lcm = vect[0].first; for (int i = 1; i < vect.Count; i++) lcm = LCM(vect[i].first, lcm); // return all numerator lcm return lcm;}// Get GCD of all the denominatorsstatic int gcdOfDemoninators(List<pair> vect){ // calculate the gcd of all the denominators int gcd = vect[0].second; for (int i = 1; i < vect.Count; i++) gcd = __gcd(vect[i].second, gcd); // return all denominator gcd return gcd;}// find lcm of all the rational numberstatic void lcmOfRationals(List<pair> vect){ // return the LCM of all numerator/ GCD of all // denominator Console.Write(lcmOfNumerator(vect)+ "/" + gcdOfDemoninators(vect));}// Driver codepublic static void Main(String[] args){ List<pair> vect = new List<pair>(); // give rational number 2/7, 3/14, 5/3 // make pair as a numerator and denominator vect.Add(new pair(2, 7)); vect.Add(new pair(3, 14)); vect.Add(new pair(5, 3)); lcmOfRationals(vect);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JAVASCRIPT program to find LCM of given arrayclass pair{ constructor(first, second) { this.first = first; this.second = second; }}// get lcm of two numbersfunction LCM(a, b) { return Math.floor((a * b) / (__gcd(a, b)));}function __gcd(a, b) { return b == 0 ? a : __gcd(b, a % b);}// Finds LCM of numeratorsfunction lcmOfNumerator(vect){ // calculate the lcm of all numerators let lcm = vect[0].first; for (let i = 1; i < vect.length; i++) lcm = LCM(vect[i].first, lcm); // return all numerator lcm return lcm;}// Get GCD of all the denominatorsfunction gcdOfDemoninators(vect){ // calculate the gcd of all the denominators let gcd = vect[0].second; for (let i = 1; i < vect.length; i++) gcd = __gcd(vect[i].second, gcd); // return all denominator gcd return gcd;}// find lcm of all the rational numberfunction lcmOfRationals(vect) { // return the LCM of all numerator/ GCD of all // denominator document.write(lcmOfNumerator(vect) + "/" + gcdOfDemoninators(vect));}// Driver codelet vect = [];// give rational number 2/7, 3/14, 5/3// make pair as a numerator and denominatorvect.push(new pair(2, 7));vect.push(new pair(3, 14));vect.push(new pair(5, 3));lcmOfRationals(vect);// This code is contributed by _SAURABH_JAISWAL</script> |
Output
30/1
Time Complexity: O(n log(min(v))), where v is the minimum element of vector
Auxiliary Space: O(1)
Please suggest if someone has a better solution which is more efficient in terms of space and time.
This article is contributed by Aarti_Rathi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
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!
