Find the largest co-prime fraction less than the given fraction

Improve Article

Save Article

Like Article

Consider the set of irreducible fractions A = {n/d | n≤d and d ≤ 10000 and gcd(n, d) = 1}. You are given a member of this set and your task is to find the largest fraction in this set less than the given fraction.

Note: This is a set and all the members are unique.

Examples:

Input: n = 1, d = 4
Output: {2499, 9997}  
Explanation: 2499/9997 is the largest fraction.

Input: n = 2, d = 4
Output: {4999, 9999}
Explanation: 4999/9999 is the largest fraction. 

Approach: The solution to the problem is based on the following mathematical concept:

Say the desired fraction is p/q. So,  

p/q < n/d
p < (n*q)/d
As we want p/q to be smaller than n/d, start to iterate over q from q = d+1.
Then for each value of q, the value of p will be floor((n*q)/d).  

Follow the below steps to implement the above idea:

  • Create two variables num and den to store the final answer. Initialize them as num =- 1 and den =1.
  • Now, loop i from d+1 to 10000:
    • Calculate the value of the fraction with denominator as i using the above observation.
    • The numerator will be (n*i)/d [this is integer division here, i.e., it gives the floor value] and denominator = i+1
    • If the fraction is greater than num/den, then update num and den accordingly.
  • After all the iterations num and den will store the required numerator and denominator.

Below is the implementation of the above approach:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

vector<int> numAndDen(int n, int d)

{

    int num = -1, den = 1;

    vector<int> ans;

  

    

    for (int i = d + 1; i <= 10000; i++) {

        int x = (n * i) / d;

        if (1.0 * x / i > 1.0 * num / den

            and __gcd(x, i) == 1)

            num = x, den = i;

    }

    ans.push_back(num);

    ans.push_back(den);

    return ans;

}

  

int main()

{

    int n = 1, d = 4;

  

    

    vector<int> ans = numAndDen(n, d);

    for (auto i : ans)

        cout << i << " ";

    return 0;

}
Output

2499 9997

Time Complexity: O(n)
Auxiliary Space: O(1)

By Julio MarchiPosted on