Given two Rational numbers, the task is to find the maximum of given two rational numbers.
Examples :
Input : first = 3/4, second= 3/2 Output : 3/2 Input : first = 100/100, second = 300/400 Output : 100/100
A simple solution is to find float values and compare the float values. The float computations may cause precision errors. We can avoid them using the below approach.
Say first = 3/2, second = 3/4
- First take a LCM of (4, 2) which is denominator of rational number. so the LCM of this is 4, then divide with both denominator and multiple with numerator of first and second respectively so the denominator value is first numerator = 6, second numerator = 3.
- Then find the max between these two. so here first numerator is max then print first rational number.
C++
// CPP program to find max between// two Rational numbers#include <bits/stdc++.h>using namespace std;struct Rational{ int nume, deno;};// Get lcm of two number'sint lcm(int a, int b) { return (a * b) / (__gcd(a, b));}// Get max rational numberRational maxRational(Rational first, Rational sec){ // Find the LCM of first->denominator // and sec->denominator int k = lcm(first.deno, sec.deno); // Declare nume1 and nume2 for get the value of // first numerator and second numerator int nume1 = first.nume; int nume2 = sec.nume; nume1 *= k / (first.deno); nume2 *= k / (sec.deno); return (nume2 < nume1)? first : sec;}// Driver Codeint main(){ Rational first = { 3, 2 }; Rational sec = { 3, 4 }; Rational res = maxRational(first, sec); cout << res.nume << "/" << res.deno; return 0;} |
Java
// JAVA program to find max between// two Rational numbersclass GFG{static class Rational{ int nume, deno; public Rational(int nume, int deno) { this.nume = nume; this.deno = deno; } };// Get lcm of two number'sstatic int lcm(int a, int b) { return (a * b) / (__gcd(a, b));}// Get max rational numberstatic Rational maxRational(Rational first, Rational sec){ // Find the LCM of first.denominator // and sec.denominator int k = lcm(first.deno, sec.deno); // Declare nume1 and nume2 for get the value of // first numerator and second numerator int nume1 = first.nume; int nume2 = sec.nume; nume1 *= k / (first.deno); nume2 *= k / (sec.deno); return (nume2 < nume1)? first : sec;}static int __gcd(int a, int b) { return b == 0 ? a:__gcd(b, a % b); }// Driver Codepublic static void main(String[] args){ Rational first = new Rational(3, 2 ); Rational sec = new Rational(3, 4 ); Rational res = maxRational(first, sec); System.out.print(res.nume+ "/" + res.deno);}}// This code is contributed by Rajput-Ji |
Python
# Python program to find max between # two Rational numbers import math# Get lcm of two number's def lcm(a, b): return (a * b) // (math.gcd(a, b)) # Get max rational number def maxRational(first, sec): # Find the LCM of first->denominator # and sec->denominator k = lcm(first[1], sec[1]) # Declare nume1 and nume2 for get the value of # first numerator and second numerator nume1 = first[0] nume2 = sec[0] nume1 *= k // (first[1]) nume2 *= k // (sec[1]) return first if (nume2 < nume1) else sec # Driver Code first = [3, 2]sec = [3, 4]res = maxRational(first, sec) print(res[0], "/", res[1], sep = "")# This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to find max between// two Rational numbersusing System;class GFG{class Rational{ public int nume, deno; public Rational(int nume, int deno) { this.nume = nume; this.deno = deno; } };// Get lcm of two number'sstatic int lcm(int a, int b) { return (a * b) / (__gcd(a, b));}// Get max rational numberstatic Rational maxRational(Rational first, Rational sec){ // Find the LCM of first.denominator // and sec.denominator int k = lcm(first.deno, sec.deno); // Declare nume1 and nume2 for get the value of // first numerator and second numerator int nume1 = first.nume; int nume2 = sec.nume; nume1 *= k / (first.deno); nume2 *= k / (sec.deno); return (nume2 < nume1)? first : sec;}static int __gcd(int a, int b) { return b == 0 ? a:__gcd(b, a % b); }// Driver Codepublic static void Main(String[] args){ Rational first = new Rational(3, 2); Rational sec = new Rational(3, 4); Rational res = maxRational(first, sec); Console.Write(res.nume + "/" + res.deno);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JAVASCRIPT program to find max between// two Rational numbersclass Rational{ constructor(nume,deno) { this.nume = nume; this.deno = deno; }}// Get lcm of two number'sfunction lcm(a,b){ return (a * b) / (__gcd(a, b)); }// Get max rational numberfunction maxRational(first,sec){ // Find the LCM of first.denominator // and sec.denominator let k = lcm(first.deno, sec.deno); // Declare nume1 and nume2 for get the value of // first numerator and second numerator let nume1 = first.nume; let nume2 = sec.nume; nume1 *= k / (first.deno); nume2 *= k / (sec.deno); return (nume2 < nume1)? first : sec;}function __gcd(a,b){ return b == 0 ? a:__gcd(b, a % b); }// Driver Codelet first = new Rational(3, 2 );let sec = new Rational(3, 4 );let res = maxRational(first, sec);document.write(res.nume+ "/" + res.deno);// This code is contributed by rag2127</script> |
Output
3/2
Time Complexity: O(log(max(deno,nume)))
Auxiliary Space: O(1)
An approach that works in constant time:
Let two rational number
First rational number => a / b –(i)
Second rational number => c / d –(ii)Lets assume First rational number is greater than second rational number
=> a/b > c/d –(iii)
Multiplying with (d*b) on the both side of inequality => a*d > c*b –(iv)Equation (iv) shows that if first rational number is greater than second than it will always hold the (iv) enquality.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;struct Rational{ int nume, deno;};Rational maxRational(Rational first, Rational second){ int a= first.nume; int b= first.deno; int c= second.nume; int d= second.deno; if((a*d) > (b*c)) return first; else return second;} int main(){ Rational first = {3, 4}; Rational second = {3, 2}; Rational res = maxRational(first, second); cout << res.nume << "/" << res.deno; return 0;} |
Java
// Java code to implement above approachimport java.util.*;public class GFG { static class Rational { int nume, deno; Rational(int num, int den) { nume = num; deno = den; } }; static Rational maxRational(Rational first, Rational second) { int a = first.nume; int b = first.deno; int c = second.nume; int d = second.deno; if ((a * d) > (b * c)) return first; else return second; } public static void main(String[] args) { Rational first = new Rational(3, 4); Rational second = new Rational(3, 2); Rational res = maxRational(first, second); System.out.println(res.nume + "/" + res.deno); }}// This code is contributed by Karandeep1234 |
Python3
import mathdef maxRational(first, second): a = first[0]; b = first[1]; c = second[0]; d = second[1]; if((a*d) > (b*c)): return first; else: return second; first = [3, 4];second = [3, 2];res = maxRational(first, second);print(res[0],"/",res[1]); # This code is contributed by poojaagarwal2. |
C#
using System;class GFG { class Rational { public int nume, deno; public Rational(int nume, int deno) { this.nume = nume; this.deno = deno; } } static Rational maxRational(Rational first, Rational second){ int a= first.nume; int b= first.deno; int c= second.nume; int d= second.deno; if((a*d) > (b*c)) return first; else return second; } public static void Main(String[] args) { Rational first = new Rational(3, 4); Rational second = new Rational(3, 2); Rational res = maxRational(first, second); Console.Write(res.nume + "/" + res.deno); }}// This code is contributed by ritaagarwal. |
Javascript
// JavaScript code to implement above approachclass Rational{ constructor(num, den){ this.nume = num; this.deno = den; }}function maxRational(first, second){ let a = first.nume; let b = first.deno; let c = second.first; let d = second.deno; if((a*d) > (b*c)) return first; else return second;}// Driver Codelet first = new Rational(3,4);let second = new Rational(3,2);let res = maxRational(first, second);document.write(res.nume + "/" + res.deno);// This code is contributed by Yash Agarwal |
Output
3/2
Time Complexity: O(1)
Auxiliary Space: O(1)
Please suggest if someone has a better solution that is more efficient in terms of space and time.
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!
