Find the largest co-prime fraction less than the given fraction in Java
The problem of finding the largest co-prime fraction less than a given fraction, involves identifying the largest fraction that has no common factors with the given fraction (except 1). Two numbers are co-prime (or relatively prime) if there is no common factor greater than one among them. In terms of fractions, the co-prime number is the kind of number whose numerator and denominator contain no common factors other than 1.
Example:
Input
n = 1, d = 4
Output
{2499, 9997}
Explanation
Starting from d + 1 = 5, the code iterates through all possible denominators up to 10000. For each denominator i, it calculates x = (n * i) / d, where n = 1 and d = 4. It checks if x/i is larger than the previous fraction and if x and i are co-prime (gcd(x, i) == 1). If both conditions are met, it updates the numerator num and denominator den. After the loop ends, the code returns the largest co-prime fraction found, which is {2499, 9997}.
Approach 1: Iterative Search Approach
Iterative Search approach iteratively searches for the largest co-prime fraction by trying different denominators greater than the given denominator d and calculating corresponding numerators. It selects the largest co-prime fraction found during the iteration. We will calculate the greatest common divisor (GCD) of two numbers using the Euclidean algorithm which is crucial for determining whether two numbers are coprime.
Algorithm
Step 1: Define a function gcd(a, b) to calculate the greatest common divisor (GCD) of two numbers using the Euclidean algorithm: If b is 0, return a. Otherwise, return gcd(b, a % b).
Step 2: Define a function largestCoPrimeFraction(n, d) to find the largest co-prime fraction less than the given fraction:
Step 2.1: Initialize num = -1 and den = 1. These variables will store the numerator and denominator of the largest co-prime fraction found so far.
Step 3: Initialize an ArrayList ans to store the result. Loop from d + 1 to an upper limit (in this case, 10000):
Step 3.1: Calculate the numerator x such that the resulting fraction x/i is greater than the given fraction n/d, x = (n * i) / d.
Step 4: Check if the current fraction x/i is greater than the previous one (num/den) and if the numerator and denominator are co-prime.
Step 5: If 1.0 * x / i > 1.0 * num / den and gcd(x, i) == 1. Update num = x and den = i. Add num and den to the ArrayList ans and return ans.
Step 6: In the main method, initialize the numerator n and denominator d. Call the largestCoPrimeFraction(n, d) function to find the largest co-prime fraction. Print the result.
Filename: LargestCoPrimeFraction.java
import java.util.ArrayList; public class LargestCoPrimeFraction { // Function to calculate the greatest common divisor (GCD) using the Euclidean algorithm public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find the largest co-prime fraction less than the given fraction public static ArrayListlargestCoPrimeFraction(int n, int d) { int num = -1; // Initialize the numerator of the largest co-prime fraction int den = 1; // Initialize the denominator of the largest co-prime fraction ArrayList ans = new ArrayList<>(); // Resultant ArrayList to store numerator and denominator // Loop to iterate over possible denominators for (int i = d + 1; i <= 10000; i++) { // Calculate the numerator such that the resulting fraction is greater than the given fraction int x = (n * i) / d; // Check if the current fraction is greater than the previous one and if the numerator and denominator are co-prime if (1.0 * x / i > 1.0 * num / den && gcd(x, i) == 1) { num = x; // Update the numerator den = i; // Update the denominator } } ans.add(num); // Add the numerator to the result ans.add(den); // Add the denominator to the result return ans; // Return the result } // Main method to test the approach public static void main(String[] args) { int n = 1; // Numerator of the given fraction int d = 4; // Denominator of the given fraction // Call the function to find the largest co-prime fraction ArrayList result = largestCoPrimeFraction(n, d); // Print the result System.out.println("Largest co-prime fraction less than " + n + "/" + d + " is: " + result.get(0) + "/" + result.get(1)); } }
Output:
Largest co-prime fraction less than 1/4 is: 2499/9997
Time Complexity
Inside the loop of numAndDen function, calculating the numerator and checking for co-prime involves basic arithmetic operations and a call to the gcd function, this operation is also constant time. Thus, the overall time complexity of the numAndDen function is O(log(min(x, i))), where x is the numerator calculated in each iteration.
Space Complexity
The space complexity of the provided code is constant because it does not use any additional space that grows with the input size. The space complexity is O(1) for both the gcd function and the numAndDen function.