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 so all the members are unique.
Example 1:
Input: n = 1, d = 8
Output: 1249 9993
Explanation: 1/8 >= 1249/9993 and this 
is the largest fraction. 
Example 2:
Input: n = 2, d = 53
Output: 377 9991
Explanation: 2/53 >= 377/9991 and this is 
the largest fraction.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function LargestFraction() which takes n and d as input parameter and returns the largest irreducible fraction in a list where the first element denotes the numerator and second elements denotes the denominator of the fraction.
Expected Time Complexity: O(K) where K <= 10000
Expected Space Complexity: O(1)
Constraints: 
1 <= n <= d <= 10000

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

	def LargestFraction(self, n, d):

		# Code here

Solutions:
import math

class Solution:

	def LargestFraction(self, n, d):
		num = 0
		den = 1
		q = 10000
		while q >= 2:
			p = (n * q - 1) // d
			if p * den >= q * num:
				num = p
				den = q
			q -= 1
		g = math.gcd(num, den)
		return (num // g, den // g)


import math

class Solution:

	def LargestFraction(self, n, d):
		if n == 1 and d == 1:
			return [9999, 10000]
		q = 1
		num = -1
		den = 1
		while q <= 10000:
			p = n * q // d
			if 1.0 * num / den < 1.0 * p / q and 1.0 * p / q < 1.0 * n / d and (math.gcd(p, q) == 1):
				num = p
				den = q
			q += 1
		return [num, den]


import math

class Solution:

	def LargestFraction(self, n, d):
		max_deno = 10000
		result_num = 0
		result_deno = 1
		for i_deno in range(max_deno, 1, -1):
			i_num = int((n * i_deno - 1) / d)
			if math.gcd(i_num, i_deno) == 1 and i_num * result_deno > result_num * i_deno:
				result_num = i_num
				result_deno = i_deno
		return [result_num, result_deno]


class Solution:

	def LargestFraction(self, n, d):
		p_dash = 0
		q_dash = 1
		for q in range(1, 10001):
			p = (n * q - 1) // d
			if p * q_dash > q * p_dash:
				p_dash = p
				q_dash = q
		hcf = self.gcd(p_dash, q_dash)
		return [p_dash // hcf, q_dash // hcf]

	def gcd(self, a, b):
		if a == 0:
			return b
		return self.gcd(b % a, a)


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)

	def LargestFraction(self, n, d):
		if n == d:
			return [9999, 10000]
		(max_frac, maxk) = (0, 0)
		for k in range(10000, 1, -1):
			if k == d:
				continue
			num = int(n / d * k)
			if self.gcd(num, k) == 1 and num / k >= max_frac:
				max_frac = num / k
				maxk = k
		return [int(n / d * maxk), maxk]


class Solution:

	def LargestFraction(self, n, d):
		if n == 1 and d == 1:
			return (9999, 10000)
		f = 0
		f1 = n / d
		a = b = 1
		for i in range(1, 10001):
			j = int(f1 * i)
			if j / i > f and j / i < f1:
				f = j / i
				a = j
				b = i
		return (a, b)


class Solution:

	def LargestFraction(self, n, d):
		check = n / d
		if n == d:
			return [9999, 10000]
		(ans1, ans2) = (1, 10000)
		for den in range(10000, 0, -1):
			num = den * n // d
			hcf = self.gcd(num, den)
			if hcf == 1 and num / den > ans1 / ans2:
				if num / den < check:
					ans1 = num
					ans2 = den
		return [ans1, ans2]

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)


import math

class Solution:

	def LargestFraction(self, n, d):
		nume = 0
		deno = 1
		q = 10000
		while q >= 2:
			p = (n * q - 1) // d
			if p * deno >= q * nume:
				nume = p
				deno = q
			q -= 1
			g = math.gcd(nume, deno)
		return (nume // g, deno // g)


class Solution:

	def LargestFraction(self, n, d):
		num = 0
		deno = 1
		for q in range(1, 10001):
			p = (n * q - 1) // d
			if p * deno > q * num:
				num = p
				deno = q
		_gcd = self.gcd(num, deno)
		return [num // _gcd, deno // _gcd]

	def gcd(self, a, b):
		if a == 0:
			return b
		return self.gcd(b % a, a)


class Solution:

	def LargestFraction(self, n, d):
		num = 0
		den = 1
		for i in range(10000, 1, -1):
			p = (n * i - 1) // d
			if p * den >= num * i:
				den = i
				num = p
		a = num
		b = den
		while b != 0:
			(a, b) = (b, a % b)
		return [int(num / a), int(den / a)]


import math

class Solution:

	def LargestFraction(self, n, d):
		num = 0
		den = 1
		for i in range(10000, 1, -1):
			p = (n * i - 1) // d
			if p * den >= i * num:
				den = i
				num = p
		gcd = math.gcd(num, den)
		return [num // gcd, den // gcd]


class Solution:

	def LargestFraction(self, n, d):
		if n == 1 and d == 1:
			return [9999, 10000]
		from math import gcd
		num = -1
		den = 1
		x = i = 0
		for i in range(10000, 1, -1):
			x = (n * i - 1) // d
			if gcd(x, i) == 1 and 1.0 * x * den > 1.0 * i * num:
				num = x
				den = i
		return [num, den]


class Solution:

	def FindingGCD(self, x, y):
		if y == 0:
			return x
		else:
			return self.FindingGCD(y, x % y)

	def LargestFraction(self, n, d):
		(a, b) = (0, 1)
		for i in range(10000, 1, -1):
			p = (n * i - 1) // d
			if p * b > i * a:
				a = p
				b = i
		g = self.FindingGCD(a, b)
		return (a // g, b // g)


from math import gcd

class Solution:

	def LargestFraction(self, n, d):
		num = 0
		den = 1
		for q in range(10000, 3, -1):
			p = (n * q - 1) // d
			if p * den >= num * q:
				den = q
				num = p
		tot = gcd(num, den)
		ans = []
		ans.append(num // tot)
		ans.append(den // tot)
		return ans


import math

class Solution:

	def LargestFraction(self, n, d):
		num = 0
		den = 1
		q = 10000
		while q >= 2:
			p = (n * q - 1) // d
			if p * den >= q * num:
				num = p
				den = q
			q -= 1
		g = math.gcd(num, den)
		return (num // g, den // g)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, d) = input().split()
		n = int(n)
		d = int(d)
		ob = Solution()
		ans = ob.LargestFraction(n, d)
		for _ in ans:
			print(_, end=' ')
		print()


import math

class Solution:

	def LargestFraction(self, n, d):
		(num, deno) = (0, 1)
		ans = list()
		for q in range(10000, 1, -1):
			p = (n * q - 1) // d
			if p * deno >= q * num:
				deno = q
				num = p
		gcd = math.gcd(num, deno)
		ans.append(num // gcd)
		ans.append(deno // gcd)
		return ans