Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. The fractions can be in any order.
 
Example 1:
Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
Example 2:
Input: n = 3
Output: ["1/2","1/3","2/3"]

Example 3:
Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".
Example 4:
Input: n = 1
Output: []

 
Constraints:

1 <= n <= 100

Source: leetcode | Difficulty: MEDIUM
Tags: Number theory

Mathematics

String algorithms

Starter code: class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        

Solutions:
class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		fractions = []
		decimals = set()
		for denom in range(1, n + 1):
			for num in range(1, denom + 1):
				if num % denom != 0 and num / denom not in decimals:
					decimals.add(num / denom)
					fractions.append(str(num) + '/' + str(denom))
		return fractions


import math

class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:

		def recurse(curr_n):
			if curr_n == 1:
				return []
			else:
				curr_arr = []
				init_val = '1/' + str(curr_n)
				curr_arr.append(init_val)
				for i in range(2, curr_n):
					denom = str(curr_n)
					if math.gcd(curr_n, i) == 1:
						numer = str(i)
						val = numer + '/' + denom
						curr_arr.append(val)
				return curr_arr + recurse(curr_n - 1)
		return recurse(n)


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		res = []
		for i in range(1, n):
			for j in range(i + 1, n + 1):
				if self.gcd(i, j) == 1:
					res.append(str(i) + '/' + str(j))
		return res

	def gcd(self, a, b):
		while b:
			(a, b) = (b, a % b)
		return abs(a)


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		r = set()
		for i in range(2, n + 1):
			for j in range(1, i):
				cd = gcd(i, j)
				r.add(str(j // cd) + '/' + str(i // cd))
		return r


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		res = []
		s = set()
		for i in range(1, n + 1):
			for j in range(1, i):
				if i % j != 0 or j == 1:
					if j / i not in s:
						res.append(str(j) + '/' + str(i))
						s.add(j / i)
		return res


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		ret = []

		def gcd(numerator, denominator):
			if numerator == 0:
				return denominator
			return gcd(denominator % numerator, numerator)
		for numerator in range(1, n + 1):
			for denominator in range(numerator + 1, n + 1):
				if numerator != denominator:
					if gcd(numerator, denominator) == 1:
						ret.append(str(numerator) + '/' + str(denominator))
		return ret


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:

		def gcd(a, b):
			if a < b:
				(a, b) = (b, a)
			while b != 0:
				(a, b) = (b, a % b)
			return a
		sol = []
		for denom in range(2, n + 1):
			for numer in range(1, denom):
				if numer == 1 or gcd(numer, denom) == 1:
					sol.append(str(numer) + '/' + str(denom))
		return sol


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		outputs = []
		for i in range(2, n + 1):
			for j in range(1, i):
				if self._gcd(i, j) == 1:
					outputs.append(f'{j}/{i}')
		return outputs

	def _gcd(self, i: int, j: int):
		if i > j:
			(i, j) = (j, i)
		res = j % i
		if res == 0:
			return i
		else:
			return self._gcd(i, res)


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

class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		res = []
		for i in range(1, n + 1):
			for j in range(i + 1, n + 1):
				if gcd(i, j) == 1:
					res.append('{}/{}'.format(i, j))
		return res


class Solution:

	def findGCD(self, a: int, b: int) -> int:
		(a, b) = (a, b) if a > b else (b, a)
		while a != 1 or b != 1:
			if a % b:
				(a, b) = (b, a % b)
			else:
				break
		return b

	def simplifiedFractions(self, n: int) -> List[str]:
		ret = set()
		for denominator in range(2, n + 1):
			for numerator in range(1, denominator):
				gcd = self.findGCD(denominator, numerator)
				ret.add(f'{numerator // gcd}/{denominator // gcd}')
		return list(ret)


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		res = []
		for idx in range(2, n + 1):
			for idx2 in range(1, idx):
				if idx2 == 1 or self.get_gcd(idx, idx2) == 1:
					res.append('{}/{}'.format(idx2, idx))
		return res

	def get_gcd(self, num1, num2):
		if num1 % num2 == 0:
			return num2
		return self.get_gcd(num2, num1 % num2)


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		ret = set()

		def gcd(a, b):
			while True:
				q = a // b
				r = a - b * q
				if r == 0:
					return b
				a = b
				b = r
		for i in range(2, n + 1):
			for j in range(1, i):
				t = gcd(i, j)
				ret.add(f'{j // t}/{i // t}')
		return list(ret)


class Solution:

	def gcd(self, a, b):
		c = 1
		while c != 0:
			c = a % b
			a = b
			b = c
		return a

	def simplify(self, a, b):
		d = self.gcd(a, b)
		return (a // d, b // d)

	def simplifiedFractions(self, n):
		fractions = set()
		for denom in range(1, n + 1):
			for num in range(1, denom):
				expr = '%d/%d' % self.simplify(num, denom)
				if expr not in fractions:
					fractions.add(expr)
		return list(fractions)


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		l = []
		for i in range(2, n + 1):
			for j in range(1, i):
				if math.gcd(i, j) < 2:
					l += [f'{j}/{i}']
		return l


class Solution:

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

	def simplifiedFractions(self, n: int) -> List[str]:
		res = []
		for d in range(2, n + 1):
			for n in range(1, d):
				if self.euclid(n, d) > 1:
					continue
				res.append(str(n) + '/' + str(d))
		return res


class Solution:

	def simplifiedFractions(self, n):
		res = []
		tmp = set()
		for i in range(1, n + 1):
			for x in range(1, i + 1):
				if x % i != 0 and x / i not in tmp:
					tmp.add(x / i)
					res.append(str(x) + '/' + str(i))
		return res


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		ans = set()
		for m in range(2, n + 1):
			for i in range(1, m):
				d = math.gcd(i, m)
				if d > 1:
					ans.add(f'{i // d}/{m // d}')
				else:
					ans.add(f'{i}/{m}')
		return ans


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		ans = []
		q = deque([])
		for i in range(2, n + 1):
			q.append((1, i))
		while q:
			(x, y) = q.popleft()
			if x == 1 or math.gcd(x, y) == 1:
				ans.append(f'{x}/{y}')
			if x + 1 < y:
				q.append((x + 1, y))
		return ans


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		fin = []
		for i in range(2, n + 1):
			for j in range(1, i):
				if gcd(i, j) == 1:
					fin.append(str(j) + '/' + str(i))
		return fin


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		res = []

		def gcd(x, y):
			while y:
				(x, y) = (y, x % y)
			return x
		for i in range(1, n + 1):
			for j in range(1, i):
				if gcd(i, j) == 1:
					res.append(str(j) + '/' + str(i))
		return res


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		added = set()
		result = []
		for denominator in range(2, n + 1):
			for i in range(1, denominator):
				if i / denominator in added:
					continue
				added.add(i / denominator)
				result.append(f'{i}/{denominator}')
		return result


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		output = []
		for n in range(2, n + 1):
			for m in range(1, n):
				if math.gcd(n, m) == 1:
					output.append(str(m) + '/' + str(n))
		return output


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:

		def gcd(a: int, b: int) -> int:
			if a < b:
				(a, b) = (b, a)
			if b == 0:
				return a
			return gcd(b, a % b)
		out = []
		for denom in range(2, n + 1):
			for num in range(1, denom):
				if gcd(denom, num) == 1:
					out.append(str(num) + '/' + str(denom))
		return out


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:

		def hasFactor(divisor, dividend):
			for i in range(2, divisor + 1):
				if dividend % i == 0 and divisor % i == 0:
					return True
			return False

		def fractions(result, i):
			for k in range(1, i):
				if k > 1 and hasFactor(k, i):
					continue
				result.append(str(k) + '/' + str(i))
		result = []
		for i in range(2, n + 1):
			fractions(result, i)
		return result
		print(result)


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		if n < 2:
			return []
		else:
			res = []
			dicts = {}
			grid = [1] * n
			grid[0] = 0
			for i in range(1, n):
				target = i + 1
				if grid[target - 1] == 1:
					dicts[target] = {target: 1}
					start = target * 2
					while start <= n:
						grid[start - 1] = 0
						dicts[target][start] = 1
						start += target
			for i in range(2, n + 1):
				res.append('1/' + str(i))
				for j in range(2, i):
					found = True
					de = j
					candidates = []
					for (key, value) in list(dicts.items()):
						if de in value:
							candidates.append(key)
					for can in candidates:
						if i in dicts[can]:
							found = False
							break
					if found:
						res.append(str(j) + '/' + str(i))
			return res


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:

		def gcd(a, b):
			for i in range(a):
				if b % (a - i) == 0 and a % (a - i) == 0:
					return a - i
		ans = []
		for i in range(2, n + 1):
			for j in range(1, i):
				if gcd(j, i) == 1:
					ans.append(f'{j}/{i}')
		return ans


from collections import defaultdict
import math

class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		if n == 1:
			return []
		numer = defaultdict(list)
		for i in range(2, 101):
			for j in range(1, i):
				if math.gcd(i, j) == 1:
					numer[i].append(j)
		ans = []
		for i in range(2, n + 1):
			for j in numer[i]:
				ans.append(f'{j}/{i}')
		print(ans)
		return ans


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:

		def maxm(n1, n2):
			temp = min(n1, n2)
			while temp:
				if n1 % temp == 0 and n2 % temp == 0:
					return temp
				temp -= 1
		res = []
		for j in range(2, n + 1):
			for i in range(1, j):
				if maxm(j, i) > 1:
					continue
				res.append(str(i) + '/' + str(j))
		return res


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		fractions = set()
		for i in range(2, n + 1):
			for j in range(1, i):
				denom = i
				num = j
				changed = True
				while changed:
					changed = False
					for k in range(2, num + 1):
						if denom % k == 0 and num % k == 0:
							denom = denom // k
							num = num // k
							changed = True
				fractions.add(str(num) + '/' + str(denom))
		return [i for i in fractions]


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:

		def gcd(i, j):
			(i, j) = sorted([i, j])
			if j % i == 0:
				return i
			return gcd(i, j % i)
		res = []
		for d in range(1, n + 1):
			for n in range(1, n + 1):
				if 0 < n / d < 1 and gcd(d, n) == 1:
					res.append('{}/{}'.format(n, d))
		return res


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		if n < 2:
			return []
		if n == 2:
			return ['1/2']
		ans = []
		record = {}
		for i in range(2, n):
			a = 1
			b = i
			while b <= n:
				for c in range(1, b):
					if c / b not in record:
						ans.append('{}/{}'.format(c, b))
						record[c / b] = True
				b += 1
		return ans


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		out = []
		visited = set()
		if n == 1:
			return out
		for i in range(2, n + 1):
			for j in range(1, i):
				tmp = f'{j}/{i}'
				if eval(tmp) not in visited:
					visited.add(eval(tmp))
					out.append(tmp)
		return out


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		res = []
		num_res = []
		for i in range(1, n + 1):
			for j in range(1, i):
				if i / j not in num_res:
					res.append(str(j) + '/' + str(i))
					num_res.append(i / j)
		return res


import itertools

class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		res = []
		num_res = []
		for (i, j) in itertools.permutations(range(1, n + 1), 2):
			if i / j < 1 and i / j not in num_res:
				res.append(str(i) + '/' + str(j))
				num_res.append(i / j)
		return res


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:

		def gcd(a, b):
			if a < b:
				return gcd(b, a)
			while b > 0:
				tmp = a % b
				a = b
				b = tmp
			return a
		ans = []
		if -1 < n < 2:
			return ans
		for i in range(1, n):
			for j in range(i + 1, n + 1):
				if i != j:
					x = gcd(i, j)
					n1 = i
					n2 = j
					if i % x == 0 == j % x and x > 1:
						n1 //= x
						n2 //= x
					st = f'{n1}/{n2}'
					if st not in ans:
						ans.append(st)
		return ans


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		from fractions import Fraction
		p = []
		if n == 1:
			return
		for numerator in range(1, n):
			k = str(1) + '/' + str(numerator + 1)
			p.append(k)
		for numerator in range(2, n + 1):
			for denominator in range(numerator + 1, n + 1):
				b = Fraction(numerator, denominator)
				b = str(b)
				if b not in p:
					k = str(numerator) + '/' + str(denominator)
					p.append(k)
		return p

def isprime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True


from math import gcd

class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		ret = []
		for numerator in range(1, n + 1):
			for denominator in range(numerator + 1, n + 1):
				if numerator != denominator:
					if gcd(numerator, denominator) == 1:
						ret.append(str(numerator) + '/' + str(denominator))
		return ret


class Solution:

	def simplifiedFractions(self, n: int) -> List[str]:
		if n == 1:
			return []

		def gcd(a, b):
			while b > 0:
				r = a % b
				a = b
				b = r
			return a
		ret = []
		for deno in range(2, n + 1):
			for nume in range(1, deno):
				g = gcd(deno, nume)
				n = nume // g
				d = deno // g
				val = str(n) + '/' + str(d)
				if val not in ret:
					ret.append(val)
		return ret