Find the closest Fraction to given fraction having minimum absolute difference
Given three integers x, y, and n, the task is to find such a pair of integers a, ?b (1?<=?b?<=?n; 0?<=?a) that the value |x/y – a/b| is as minimal as possible, where |x| represents the absolute value of x.
Examples:
Input: x = 3, y = 7, n = 6
Output: 2/5
Explanation: a=2 and b=5 and b<=6 then 3/7 – 2/5 = 1/35, which is the minimum difference possibleInput: x = 12, y = 37, n = 5
Output: 1/3
Approach: Iterate over the denominator. Let the denominator be i. Then it is required to choose such a numerator d such that |x/y – d/i| is minimal. d = (x*i)/y is a good choice. Also check for d+1. While updating the answer from A/B to d/i, check if x/y – d/i < x/y -A/B or (B*x-y*A) * (i*y) > (i*x-y*d) * (B*y). Follow the steps below to solve the problem:
- Initialize the variables A and B as -1 to store the answers.
- Iterate over the range [1, N] using the variable i and perform the following steps:
- Initialize the variable d as (i*x)/y as the closest possible numerator.
- If d is greater than equal to 0 and A is equal to -1 or ABS(B * x – y * A) * ABS(i * y) is greater than ABS(i * x – y * d) * ABS(B * y), then set the value of A as d and B as i.
- Increase the value of d by 1.
- If d is greater than equal to 0 and A is equal to -1 or ABS(B * x – y * A) * ABS(i * y) is greater than ABS(i * x – y * d) * ABS(B * y), then set the value of A as d and B as i.
- After performing the above steps, print the value of A/B as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the absolute // value of x long long ABS( long long x) { return max(x, -x); } // Function to find the fraction with // minimum absolute difference void findFraction( long long x, long long y, long long n) { // Initialize the answer variables long long A = -1, B = -1; // Iterate over the range for ( long long i = 1; i <= n; i++) { // Nearest fraction long long d = (i * x) / y; // x/y - d/i < x/y -A/B //(B*x-y*A) * (i*y) > (i*x-y*d) * (B*y) if (d >= 0 && (A == -1 || ABS(B * x - y * A) * ABS(i * y) > ABS(i * x - y * d) * ABS(B * y))) A = d, B = i; // Check for d+1 d++; if (d >= 0 && (A == -1 || ABS(B * x - y * A) * ABS(i * y) > ABS(i * x - y * d) * ABS(B * y))) A = d, B = i; } // Print the answer cout << A << "/" << B << endl; } // Driver Code int main() { long long x = 3, y = 7, n = 6; findFraction(x, y, n); return 0; } |
Java
// Java code for the above approach import java.io.*; class GFG { // Function to find the absolute // value of x static long ABS( long x) { return Math.max(x, -x); } // Function to find the fraction with // minimum absolute difference static void findFraction( long x, long y, long n) { // Initialize the answer variables long A = - 1 , B = - 1 ; // Iterate over the range for ( long i = 1 ; i <= n; i++) { // Nearest fraction long d = (i * x) / y; // x/y - d/i < x/y -A/B //(B*x-y*A) * (i*y) > (i*x-y*d) * (B*y) if (d >= 0 && (A == - 1 || ABS(B * x - y * A) * ABS(i * y) > ABS(i * x - y * d) * ABS(B * y))) A = d; B = i; // Check for d+1 d++; if (d >= 0 && (A == - 1 || ABS(B * x - y * A) * ABS(i * y) > ABS(i * x - y * d) * ABS(B * y))) A = d; B = i; } A--; B--; // Print the answer System.out.println(A + "/" + B); } // Driver Code public static void main(String[] args) { long x = 3 ; long y = 7 ; long n = 6 ; findFraction(x, y, n); } } // This code is contributed by lokeshpotta. |
Python3
# Python3 program for the above approach # Function to find the absolute # value of x def ABS (x): return max (x, - x) # Function to find the fraction with # minimum absolute difference def findFraction(x, y, n): # Initialize the answer variables A = - 1 B = - 1 # Iterate over the range for i in range ( 1 , n + 1 ): # Nearest fraction d = (i * x) / / y # x/y - d/i < x/y -A/B # (B*x-y*A) * (i*y) > (i*x-y*d) * (B*y) if (d > = 0 and (A = = - 1 or ABS (B * x - y * A) * ABS (i * y) > ABS (i * x - y * d) * ABS (B * y))): A = d B = i # Check for d+1 d + = 1 if (d > = 0 and (A = = - 1 or ABS (B * x - y * A) * ABS (i * y) > ABS (i * x - y * d) * ABS (B * y))): A = d B = i # Print the answer print ( str (A) + "/" + str (B)) # Driver Code if __name__ = = '__main__' : x = 3 y = 7 n = 6 findFraction(x, y, n) # This code is contributed by mohit kumar 29 |
C#
// C# code for the above approach using System; public class GFG{ // Function to find the absolute // value of x static long ABS( long x) { return Math.Max(x, -x); } // Function to find the fraction with // minimum absolute difference static void findFraction( long x, long y, long n) { // Initialize the answer variables long A = -1, B = -1; // Iterate over the range for ( long i = 1; i <= n; i++) { // Nearest fraction long d = (i * x) / y; // x/y - d/i < x/y -A/B //(B*x-y*A) * (i*y) > (i*x-y*d) * (B*y) if (d >= 0 && (A == -1 || ABS(B * x - y * A) * ABS(i * y) > ABS(i * x - y * d) * ABS(B * y))) A = d; B = i; // Check for d+1 d++; if (d >= 0 && (A == -1 || ABS(B * x - y * A) * ABS(i * y) > ABS(i * x - y * d) * ABS(B * y))) A = d; B = i; } A--; B--; // Print the answer Console.Write(A + "/" + B); } // Driver Code static public void Main (){ long x = 3; long y = 7; long n = 6; findFraction(x, y, n); } } // This code is contributed by shubhamsingh10. |
Javascript
<script> // JavaScript program for the above approach // Function to find the absolute // value of x function ABS(x) { return Math.max(x, -x); } // Function to find the fraction with // minimum absolute difference function findFraction(x, y, n) { // Initialize the answer variables let A = -1, B = -1; // Iterate over the range for (let i = 1; i <= n; i++) { // Nearest fraction let d = Math.floor((i * x) / y); // x/y - d/i < x/y -A/B //(B*x-y*A) * (i*y) > (i*x-y*d) * (B*y) if (d >= 0 && (A == -1 || ABS(B * x - y * A) * ABS(i * y) > ABS(i * x - y * d) * ABS(B * y))) A = d; B = i; // Check for d+1 d++; if (d >= 0 && (A == -1 || ABS(B * x - y * A) * ABS(i * y) > ABS(i * x - y * d) * ABS(B * y))) A = d; B = i; } A--; B--; // Print the answer document.write(A + "/" + B); } // Driver code let x = 3; let y = 7; let n = 6; findFraction(x, y, n); // This code is contributed by sanjoy_62 </script> |
2/5
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us