Find max rational number in given Array

Given the Numerator and Denominator of N Rational Numbers, the task is to find the maximum Rational Number from the array.

Examples:

Input: N = 2 num[] = { 3, 3 } den[] = { 2, 4 }
Output: 3 / 2

Input: N = 2 num[] = { 100, 300 } den[] = { 100, 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 below approach. Let num[] = { 3, 3}, den[] = { 2, 4};

• First take LCM of (2, 4) which is denomiator array. So the LCM of this is 4, then multiply LCM with fraction like (num[i] * lcm_deno) / den[i]
• Then in a loop find the max between between the rational numbers.

Below is the implementation of the above approach:

// C++ implementation to find the
// maximum Rational Number from the array

#include <bits/stdc++.h>
using namespace std;

// Utility function to find
// GCD of ‘a’ and ‘b’
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// Returns LCM of array elements
int findlcm(int arr[], int n)
{
    // Initialize result
    int ans = arr[0];

    // ans contains LCM of arr[0], ...arr[i]
    // after i’th iteration
    for (int i = 1; i < n; i++)
        ans = (arr[i] * ans) / gcd(arr[i], ans);

    return ans;
}

// Print the maximum Rational Number from the array
void maxRationalNum(int n, int num[], int den[])
{
    // Finding LCM of denominator array
    int lcm_deno = findlcm(den, n);

    // To store maximum rational number
    int mx = -1;
    int max_numerator = -1;
    int max_denominator = -1;

    // Finding the product of all numerators and denominators
    for (int i = 0; i < n; i++) {
        int number = (num[i] * lcm_deno) / den[i];
        if (mx < number) {
            mx = number;
            max_numerator = num[i];
            max_denominator = den[i];
        }
    }

    // Printing the max rational number
    cout << max_numerator << "/" << max_denominator << endl;
}

// Driver Program
int main()
{
    int n = 2;
    int num[] = {3, 3};
    int den[] = {2, 4};

    maxRationalNum(n, num, den);
    return 0;
}

Output:

3/2

Time Complexity: O(N)