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: The fraction that is given to you may or may not be irreducible.
Example 1:
Input: n = 1, d = 4
Output: {2499, 9997}  
Explanation: 2499/9997 is the largest fraction.
Example 2:
Input: n = 2, d = 4
Output: {4999, 9999}
Explanation: 4999/9999 is the largest fraction. 
Your Task:  
You dont need to read input or print anything. Complete the function numAndDen() which takes n and d as input parameter and returns the numerator and the denominator of the required irreducible fraction.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= n <= d <=1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:

	def numAndDen(self, n, d):

		# code here



Solutions:
import math as mt

class Solution:

	def numAndDen(self, n, d):
		num = -1
		den = 1
		f = d + 1
		for i in range(f, 10001):
			x = n * i // d
			if mt.gcd(x, i) == 1:
				if 1.0 * x / i > 1.0 * num / den:
					num = x
					den = i
		return (num, den)


import math

class Solution:

	def numAndDen(self, n, d):
		count = -1
		den = 1
		start = d + 1
		end = 10001
		for num in range(start, end):
			number = n * num // d
			if math.gcd(number, num) == 1:
				if 1 * number / num > 1 * count / den:
					count = number
					den = num
		return (count, den)


import math

class Solution:

	def numAndDen(self, n, d):
		num = 0
		den = 1
		for i in range(10 ** 4, d, -1):
			p = (n * i - 1) // d
			if p * den >= num * i:
				num = p
				den = i
		return [num, den]


import math

class Solution:

	def numAndDen(self, n, d):
		num = 0
		den = 1
		for q in range(10000, d, -1):
			p = (n * q - 1) // d
			if p * den >= num * q:
				den = q
				num = p
		return [num, den]


import math

class Solution:

	def numAndDen(self, n, d):
		(a, b) = (1, -1)
		for i in range(10 ** 4, d, -1):
			t = n * i // d
			if math.gcd(t, i) == 1 and t / i > a / b:
				a = t
				b = i
		return [a, b]


class Solution:

	def numAndDen(self, n, d):
		(p, q) = (10000, 10000)
		curr = n / d
		diff = 10 ** 5
		(a, b) = (0, 0)
		while p >= 1 and q >= 1:
			while p >= 1 and p / q >= curr:
				p -= 1
			while q >= 1 and p / q < curr:
				q -= 1
			if curr - p / (q + 1) < diff:
				diff = curr - p / (q + 1)
				(a, b) = (p, q + 1)
		return (a, b)


from math import gcd

class Solution:

	def numAndDen(self, n, d):
		iNum = -1
		iDen = 1
		listResult = []
		for i in range(d + 1, 10001):
			x = n * i // d
			if 1.0 * x / i > 1.0 * iNum / iDen and gcd(x, i) == 1:
				iNum = x
				iDen = i
		listResult.append(iNum)
		listResult.append(iDen)
		return listResult


class Solution:

	def numAndDen(self, n, d):
		(current_numerator, current_denominator, best_numerator, best_denominator, best_error) = (10000, 10000, 10000, 10000, 10000)
		required_ratio = n / d
		current_ratio = current_numerator / current_denominator
		while current_numerator >= 1 and current_denominator >= 1:
			while current_ratio >= required_ratio:
				current_numerator -= 1
				current_ratio = current_numerator / current_denominator
			while current_ratio < required_ratio and current_denominator > 1:
				current_denominator -= 1
				current_ratio = current_numerator / current_denominator
			if required_ratio - current_numerator / (current_denominator + 1) < best_error:
				best_numerator = current_numerator
				best_denominator = current_denominator + 1
				best_error = required_ratio - best_numerator / best_denominator
		a_gcd = self.gcd(best_numerator, best_denominator)
		return [int(best_numerator / a_gcd), int(best_denominator / a_gcd)]

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


from math import gcd

class Solution:

	def numAndDen(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 numAndDen(self, n, d):
		num = -1
		do = 1
		k = d + 1
		for i in range(d + 1, 10001):
			k = n * i // d
			if math.gcd(k, i) == 1:
				if 1.0 * k / i > 1.0 * num / do:
					num = k
					do = i
		return (num, do)


import math

class Solution:

	def numAndDen(self, n, d):
		p = 0
		temp2 = 0
		for q in range(10000, 2, -1):
			temp = n * q // d
			if temp * d < n * q and temp <= q:
				if math.gcd(temp, q) == 1:
					if temp / q * temp2 >= p:
						p = temp
						temp2 = q
		return [p, temp2]


import math

class Solution:

	def numAndDen(self, n, d):
		num = -1
		dem = 1
		for down in range(d + 1, 10001):
			up = n * down // d
			if math.gcd(up, down) == 1:
				if up / down > num / dem:
					(num, dem) = (up, down)
		return [num, dem]


class Solution:

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

	def numAndDen(self, n, d):
		maxnum = 0
		maxden = 1
		for den in range(d + 1, 10001):
			newnum = n * den // d
			if self.gcd(den, newnum) != 1:
				continue
			if newnum * maxden > maxnum * den:
				maxnum = newnum
				maxden = den
		return (maxnum, maxden)


import math

class Solution:

	def numAndDen(self, n, d):
		num = -1
		denom = 1
		temp = d + 1
		for i in range(temp, 10001):
			x = n * i // d
			if math.gcd(x, i) == 1:
				if 1.0 * x / i > 1.0 * num / denom:
					num = x
					denom = i
		return (num, denom)


class Solution:

	def numAndDen(self, n, d):
		import math
		(up, down) = (-1, 1)
		f = d + 1
		for i in range(f, 10001):
			x = n * i // d
			if math.gcd(x, i) == 1:
				if 1.0 * x / i > 1.0 * up / down:
					up = x
					down = i
		return (up, down)


from math import gcd

class Solution:

	def numAndDen(self, n, d):
		(num, den) = (-1, 1)
		for D in range(d + 1, 10001):
			N = n * D // d
			if gcd(N, D) == 1 and N / D > num / den:
				(num, den) = (N, D)
		return [num, den]


import math

class Solution:

	def numAndDen(self, n, d):
		a = -1
		b = 2
		for i in range(d + 1, 10001):
			x = i * n // d
			if math.gcd(x, i) == 1:
				if x / i > a / b:
					a = x
					b = i
		return (a, b)


class Solution:

	def numAndDen(self, n, d):
		q = 10000
		ans = 0
		anspq = (0, 0)
		for i in range(d):
			if q * n % d == 0:
				q = q - 1
				continue
			p = q * n // d
			if p / q > ans:
				ans = p / q
				anspq = (p, q)
			q -= 1
		return anspq


class Solution:

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

	def numAndDen(self, n, d):
		num = -1
		den = 1
		for i in range(d + 1, 10001):
			x = n * i // d
			if self.gcd(x, i) != 1:
				continue
			if x * den > num * i:
				num = x
				den = i
		return (num, den)


import math as mathwa

class Solution:

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

	def numAndDen(self, n, d):
		num = -1
		den = 1
		f = d + 1
		for i in range(f, 10001):
			x = n * i // d
			if self.gcd(x, i) != 1:
				continue
			if x * den > num * i:
				num = x
				den = i
		return (num, den)


import math as mt

class Solution:

	def numAndDen(self, n, d):
		nm = -1
		dn = 1
		g = d + 1
		for i in range(g, 10001):
			r = n * i // d
			if mt.gcd(r, i) == 1:
				if 1.0 * r / i > 1.0 * nm / dn:
					nm = r
					dn = i
		return (nm, dn)


import math

class Solution:

	def numAndDen(self, n, d):
		x = -1
		y = 1
		f = d + 1
		for i in range(f, 10001):
			ans = n * i // d
			if math.gcd(ans, i) == 1:
				if 1.0 * ans / i > 1.0 * x / y:
					x = ans
					y = i
		return (x, y)


class Solution:

	def numAndDen(self, n, d):
		global count1
		global count2
		count1 = []
		count2 = []
		if n == 1 and d == 10000:
			return 0
		else:
			k = 10000 / d
			n1 = round(k * n) + 1
			d1 = 10000
			while n1 > 1:
				n1 = n1 - 1
				M = n1 / d1
				while M < n / d:
					count1.append([n1, d1])
					count2.append(M)
					d1 = d1 - 1
					M = n1 / d1
			return count1[count2.index(max(count2))]


import math

class Solution:

	def numAndDen(self, n, d):
		N = -1
		D = 1
		for i in range(d + 1, 10001):
			x = n * i // d
			if math.gcd(x, i) == 1:
				if 1.0 * x / i > 1.0 * N / D:
					N = x
					D = i
		return [N, D]


class Solution:

	def numAndDen(self, n, d):
		if n < 1 or d < n or d > 1000:
			raise ValueError('Error!')
		max_div = 0
		max_n = n
		max_d = d
		for new_d in range(d, 10000):
			new_n = int(new_d * n / d)
			div = new_n / new_d
			if div == n / d:
				continue
			if div >= max_div:
				max_div = div
				max_n = new_n
				max_d = new_d
		return (max_n, max_d)


import math

class Solution:

	def numAndDen(self, n, d):
		a = -1
		b = 1
		for i in range(d + 1, 10001):
			c = n * i // d
			if math.gcd(c, i) == 1 and 1.0 * c / i > 1.0 * a / b:
				a = c
				b = i
		return (a, b)


class Solution:

	def numAndDen(self, n, d):
		a = int(n / d * 10000)
		b = 10000
		max_a = 0
		max_b = 1
		while a > 0 and b > 0:
			if a / b > n / d or a / b == n / d:
				a = a - 1
			else:
				if max_a / max_b < a / b:
					max_a = a
					max_b = b
				b = b - 1
		return [max_a, max_b]


import math

class Solution:

	def numAndDen(self, n, d):
		g = math.gcd(n, d)
		d = d // g
		n = n // g
		m = -1
		k = 1
		for i in range(10000, d, -1):
			x = n * i // d
			if math.gcd(x, i) == 1:
				if 1.0 * x / i > 1.0 * m / k:
					m = x
					k = i
		return [m, k]


import math

class Solution:

	def numAndDen(self, n, d):
		(num, den) = (-1, 1)
		for i in range(d + 1, 10001):
			x = n * i // d
			if math.gcd(x, i) == 1 and x / i > num / den:
				(num, den) = (x, i)
		return (num, den)