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

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    arr = []
    
    def simplifiedFractions(self, n: int) -> List[str]:
        ans = []
        
        if len(Solution.arr) < 2:
            Solution.arr = [[],[]]
            
        if n >= len(Solution.arr):
            for d in range(len(Solution.arr), n + 1):
                denominator = \"/\" + str(d)
                Solution.arr.append([])
                
                for num in range(1, d):
                    if gcd(num, d) == 1:
                        Solution.arr[-1].append(str(num) + denominator)
                    
                    
        for i in range(2, n + 1):
            ans += Solution.arr[i]
                
        return ans
                    
                
        

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
        if n == 1:
            return []
        k = 0
        ret = []
        for i in range(2, n + 1):
            if i in primes:
                ret += [\"%d/%d\" % (j, i) for j in range(1, i)]
            else:
                dPrimes = []
                for p in primes:
                    if p * 2 > i:
                        break
                    if i % p == 0:
                        dPrimes.append(p)
                tmp = set(range(1, i))
                for p in dPrimes:
                    for j in range(p, i, p):
                        tmp.discard(j)
                ret += [\"%d/%d\" % (j, i) for j in tmp]
        return ret

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        fractions = []
        decimals = set()
        
        for i in range(1, n + 1):
            for x in range (1, i + 1):
                if (x % i != 0 and x/i not in decimals):
                    decimals.add(x/i)
                    fractions.append(str(x) + \"/\" + str(i))
                    
        return fractions
    
            

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: # we don't want whole numbers, so num % denom != 0
                    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:
                        # cant be simplified anymore
                        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]:
        def gcd(x,y):
            while(y):
                x,y=y,x%y
            return x
    
        result = []
        for i in range(2,n+1):
            for j in range(1,i):
                if(gcd(i,j)==1):
                    result.append(str(j)+\"/\"+str(i))
        return result
                    
            
            
        

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
               
        return [f\"{j}/{d}\" for d in range(2, n+1) for j in range(1, d) if gcd(max(d,j), min(d,j)) == 1]
                    


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]:
        res = []
        for j in range(2,n+1):
            for i in range(1,j):
                if math.gcd(i,j) == 1:
                    res.append(str(i)+\"/\"+str(j))
        return res

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        res = []
        for i in range(2, n + 1):
            res.append('1/' + str(i))
        for i in range(2, 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]:
        # observations:
        # - gcd can't be anything bigger than half the number
        result = []
        seen = set()
        for i in range(2, n + 1):
            for j in range(1, i):
                gcd = math.gcd(i, j)
                c_i = i
                c_i //= gcd
                j //= gcd
                if (j, c_i) not in seen:
                    seen.add((j, c_i))
                    result.append(\"{}/{}\".format(j, c_i))
        return result

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]:
        if n == 1:
            return []
        
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
        ret = []
        
        for i in range(2, n + 1):
            if i in primes:
                ret += [\"%d/%d\" % (j, i) for j in range(1, i)]
            else:
                tmpPrimes = []
                for p in primes:
                    if p * 2 > i:
                        break
                    if i % p == 0:
                        tmpPrimes.append(p)
                tmp = set(range(1, i))
                for p in tmpPrimes:
                    for j in range(p, i, p):
                        tmp.discard(j)
                ret += [\"%d/%d\" % (j, i) for j in tmp]
        return ret

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def gcd(x, y):
            return y if x == 0 else gcd(y % x, x)
        
        return [\"%s/%s\" % (i, j) for j in range(2, n + 1) for i in range(1, j) if gcd(i, j) == 1]

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
        
        # print (gcd(6, 4))
        
        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)
                #print(i, j, t)
                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
        
#         def memoize(f):
#             memo = {}
#             def helper(x):
#                 if x not in memo:            
#                     memo[x] = f(x)
#                 return memo[x]
#             return helper
        
#         def hcf(a, b):
#             for i in range(2, a+1):
#                 if a % i == 0 and b % i == 0:
#                     return False
#             return True

#         def cal(x):
#             l = []
#             for i in range(1, x):
#                 if hcf(i, x):
#                     l += [\"{}/{}\".format(i, x)]
#             return l

#         def fib(n):
#             if n == 1:
#                 return []
#             elif n == 2:
#                 return [\"1/2\"]
#             else:
#                 return fib(n-1) + cal(n)

        
#         fib = memoize(fib)
        
#         return fib(n)


class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        simp = set()
        out = []
        for i in range(1,n+1):
            for j in range(1,i):
                if not j/i in simp:
                    out.append(f\"{j}/{i}\")
                    simp.add(j/i)
                    
        return out
        

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        seen = set()
        res = []
        for j in range(2,n+1):
            for i in range(1,j):
                if i/j not in seen:
                    seen.add(i/j)
                    res.append(str(i)+\"/\"+str(j))
        return res

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        res = []
        
        def gcd(a, b):
            if a==0:
                return b
            return gcd(b%a, a)
            
        for i in range(1, n):
            for j in range(i+1, n+1):
                if gcd(i,j)==1:
                    res.append(str(i)+\"/\"+str(j))
        
        return res

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 is_coprime(self, a, b):
        l = max(a, b)
        s = min(a, b)
        
        while s > 0:
            l,s = s, l % s
        
        return l == 1
    
    def simplifiedFractions(self, n: int) -> List[str]:
      
        
        ans = []
        for d in range(2, n+1):
            n = 1
            while n < d:
                if n == 1 or self.is_coprime(n, d):
                    ans.append(str(n) + \"/\" + str(d))
                n += 1
        
        return ans

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        res = []
        for i in range(2, n + 1) :
            for j in range(1, i) :
                if not ((i % 2 == 0) and (j % 2 == 0)) :
                    res_flag = True
                    for k in range(3, j + 1, 2):
                        if (i % k == 0) and (j % k == 0) :
                            res_flag = False
                            break
                    if res_flag : res.append(str(j) + \"/\" + str(i))
        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]:
        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]:
        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()
            #TODO: check 
            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
            


import math
class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        res = []
        if n == 1: return res
        for i in range(2,n+1):
            for j in range(1,i):
                if math.gcd(i,j) == 1: 
                    res.append(f\"{j}/{i}\")
        return res
                               
                
            
        

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]:
        def get_gcd(a, b):
            if b == 0:
                return a
            else:
                return get_gcd(b, a % b)


        fractions = set()
        for denominator in range(1, n + 1):
            for numerator in range(1, denominator):
                gcd = get_gcd(numerator, denominator)
                s_numerator = numerator // gcd
                s_denominator = denominator // gcd
                fraction = \"{}/{}\".format(s_numerator, s_denominator)
                fractions.add(fraction)

        return fractions


class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        if n == 1:
            return []
        results = []
        for deno in range(2,n+1):
            for deli in range(1,deno):
                canAdd = True
                for dev in range(2,deli+1):
                    if deno % dev == 0 and deli % dev == 0:
                        canAdd = False
                        break
                if canAdd:
                    results.append(\"{}/{}\".format(deli,deno))
        return results

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def gcd(a, b):
            if b == 0: return a
            return gcd(b, a%b)
        
        result = []
        for i in range(2, n+1):
            for j in range(i-1, 0, -1):
                if gcd(j, i) == 1:
                    result.append(\"{0}/{1}\".format(j,i))
        return result
                
        

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]:
        seen = set()
        ans = []
        
        for i in range(2,n+1):
            for j in range(1,i):
                if j / i not in seen:
                    seen.add(j/i)
                    ans.append(\"%d/%d\" % (j,i))
                    
        return ans
        

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def frac_to_string(num, den):
            return f\"{num}/{den}\"
        
        def relatively_prime(a, b):
            \"\"\" Invariant: a < b \"\"\"
            for i in range(2, a + 1):
                if a % i == 0 and b % i == 0:
                    return False
            return True
        
        ans = []
        for den in range(1, n + 1):
            for num in range(1, den):
                if relatively_prime(num, den):
                    ans.append(frac_to_string(num, den))
        return ans
        

# 3:22
class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        if n == 1:
            return []
        
        def simplified(i, n):
            for j in range(2, i + 1):
                if i % j == 0 and n % j == 0:
                    return False
            return True
        
        at_n = []
        for i in range(1, n):
            if simplified(i, n):
                at_n.append(f\"{i}/{n}\")
        
        return at_n + self.simplifiedFractions(n - 1)

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        res = []
        for num in range(2, n+1):
            for i in range(1, num):
                if i == 1 or self.valid(i, num):
                    res.append(\"{}/{}\".format(i, num))
        return res
    
    def valid(self, a, b):
        if b % a == 0:
            return False
        for x in range(2, a):
            if a % x == 0 and b % x == 0:
                return False
        return True

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        ans = []
        for i in range(2, n+1):
            for j in range(1, i):
                found = False
                for k in range(2, j+1):
                    if i % k == 0 and j % k == 0:
                        found = True
                        break
                if not found: ans.append(str(j) + \"/\" + str(i))
        return ans


class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def memoize(f):
            memo = {}
            def helper(x):
                if x not in memo:            
                    memo[x] = f(x)
                return memo[x]
            return helper
        
        def hcf(a, b):
            for i in range(2, a+1):
                if a % i == 0 and b % i == 0:
                    return False
            return True

        def cal(x):
            l = []
            for i in range(1, x):
                if hcf(i, x):
                    l += [\"{}/{}\".format(i, x)]
            return l

        def fib(n):
            if n == 1:
                return []
            elif n == 2:
                return [\"1/2\"]
            else:
                return fib(n-1) + cal(n)

        
        fib = memoize(fib)
        
        return fib(n)

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        a=[]
        for i in range(2,n+1):
            s=\"1\"+\"/\"+str(i)
            a.append(s)
        for i in range(2,n):
            for j in range(2,n+1):
                if(math.gcd(i,j)==1 and (i/j)<1):
                    s=str(i)+\"/\"+str(j)
                    a.append(s)
        return a
        

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]:
        # no solution for 1
        if n == 1:
            return []
        
        ans = []
        seen = set()
        for i in range(2, n+1):
            denom = str(i)
            for j in range(1, i):
                result = j/i
                if result in seen:
                    continue
                ans.append(str(j)+\"/\"+denom)
                seen.add(result)
        return ans
        

def gcd(x, y):
    # while y != 0:
    #     (x, y) = (y, x%y)
    # return x
    if y == 0:
        return x
    else: 
        return gcd(y, x%y)

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        ans = []
        for i in range(1,n+1):
            for j in range(i, n+1):
                if i == j: continue
                if gcd(i,j) == 1:
                    ans.append(str(i) + \"/\" + str(j))
        return ans

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x%y)
    return x

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        ans = []
        for i in range(1,n+1):
            for j in range(i, n+1):
                if i == j: continue
                if gcd(i,j) == 1:
                    ans.append(str(i) + \"/\" + str(j))
        return ans

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        
        if n == 1:
            return []
        
        rst = []
        
        dedup = set()
        
        for i in range(1, n+1):
            
            for j in range(1, i):
                
                x = j/i
                
                s = str(j) + \"/\" + str(i)
                
                print(s)
                
            
                if x not in dedup:

                    dedup.add(x)
                    rst.append(s)
                    
        return rst
        

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        result=[]
        if n == 1:
            return(result)
        for i in range(2,n+1):
            result.append(\"1/\"+str(i))
            for j in range(2,i):
                flag=0
                for k in range(2,j+1):
                    if j%k==0:
                        if i%k ==0:
                            flag=flag+1
                if flag == 0:
                    result.append(str(j)+\"/\"+str(i))
        return(result)

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


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

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

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]:
        ans = []
        for i in range(1,n+1):
            for j in range(1,i):
                if gcd(i,j) == 1:
                    ans.append(str(j)+'/'+str(i))
        return ans
    
    def gcd(a,b):
        while a:
            a,b = b%a, a
        return b

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

def gcd(a, b):\r
    # Everything divides 0\r
    if a == 0:\r
        return b\r
    if b == 0:\r
        return a\r
    # base case\r
    if a == b:\r
        return a\r
    # a is greater\r
    if a > b:\r
        return gcd(a - b, b)\r
    return gcd(a, b - a)\r
\r
\r
class Solution:\r
    def simplifiedFractions(self, n: int) -> List[str]:\r
        finals = []\r
        for i in range(1, n):\r
            for j in range(i, n + 1):\r
                if i != j:\r
                    g = gcd(i, j)\r
                    finals.append(\"{}/{}\".format(i // g, j // g))\r
        return list(set(finals))\r
\r


def gcd(a,b):     # Everything divides 0  
    if (a == 0): 
        return b 
    if (b == 0): 
        return a     # base case 
    if (a == b): 
        return a     # a is greater 
    if (a > b): 
        return gcd(a-b, b) 
    return gcd(a, b-a) 

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        finals = []
        for i in range(1, n):
            for j in range(i,n + 1):
                if i != j:
                    g = gcd(i, j)
                    finals.append(\"{}/{}\".format(i//g, j//g))        
        return list(set(finals))
        

class Solution:
    def get_ggT(self, a, b):
        while (a != b):
            a_ = a - b
            a = max(a_, b)
            b = min(a_, b)
            
        return a
        
        
        
    def simplifiedFractions(self, n: int) -> List[str]:
        ret = set()
        
        
        for denominator in range(2, n + 1):
            for numerator in range(1, denominator):
                ggT = self.get_ggT(denominator, numerator)
                ret.add(str(numerator // ggT) + \"/\" + str(denominator // ggT))
                
        return ret

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def lar_com(a,b):
            a,b=max(a,b),min(a,b)
            if b==0: return 0
            if b==1: return 1
            return lar_com(a-b,b)
            
        
        res=[]
        for i in range(2,n+1):
            for j in range(1,i):
                if lar_com(i,j)==1:
                    res.append(str(j)+\"/\"+str(i))
        return res

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def Simplify(x, y):
            for i in range(x, 1, -1):
                if x % i == 0 and y % i == 0:
                    x //= i
                    y //= i 
            return x, y
        
        res = set()
        for i in range(2, n+1):
            for j in range(1, i):
                nom, denom = j, i
                print('before', nom, denom)
                nom, denom = Simplify(nom, denom) 
                print('after', nom, denom)
                res.add(str(nom)+\"/\"+str(denom))
        return res
    
    
                
[\"1/3\",\"2/4\",\"5/6\",\"5/8\"]

[\"1/3\",\"5/6\",\"5/8\"]

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
                
        # print(ans)
        return ans

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def gcd(a, b):
            a, b = max(a, b), min(a, b)
            if b == 0:
                return a
            else:
                return gcd(b, a - b)
            
        output = []
        for den in range(1, n + 1):
            for num in range(1, den):
                if gcd(den, num) == 1:
                    output.append(\"%d/%d\" % (num, den))
        return output

from math import gcd

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        if n == 1:
            return []
        ans = []
        for i in range(1, n):
            if gcd(n, i) == 1:
                ans.append(f\"{i}/{n}\")
        ans += self.simplifiedFractions(n-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]:
        ans = []
        temp_lst = []
        temp=\"\"
        for i in range(1,n+1):
            for j in range(1,n+1):
                if j//i <1 and j/i not in temp_lst:
                    temp_lst.append(j/i)
                    #print(temp_lst)
                    temp = str(j)+\"/\"+str(i)
                    ans.append(temp)
        return ans

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
##        print(gcd(89,6))
        ans=[]
        if -1<n<2:return ans
        for i in range(1,n):
            for j in range(i+1,n+1):#pass
                if i!=j:
                    x=gcd(i,j)
##                    print(i,j,x)
##                    print(x)
                    n1=i
                    n2=j
                    if i%x==0==j%x and x>1:
                        n1//=x
                        n2//=x
##                    st=(i,j)
##                    print(st)
                    st=f'{n1}/{n2}'
                    if st not in ans:
                        ans.append(st)
##        ans.sort()
##        print(ans)
##        for i,an in enumerate(ans):
##            ans[i]=f'{an[0]}/{an[1]}'
                        
        return ans

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]:
        result_str = []
        result_num = []
        for i in range(1, n+1):
            for j in range(1, i):
                if j/i not in result_num:
                    result_num.append(j/i)
                    result_str.append(\"{}/{}\".format(j, i))
        return result_str
                
        

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):
    # Corner cases 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
  
    # This is checked so that we can skip  
    # middle five numbers in below loop 
    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
        
                    


class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        lo=[i for i in range(2,n+1)]
        hi=[i for i in range(1,n)]
        res=[]
        dic=[]
        for i in range(len(lo)):
            for j in range(len(hi)):
                if hi[j]/lo[i] not in dic and hi[j]<lo[i]:
                    dic.append(hi[j]/lo[i])
                    res.append(str(hi[j])+\"/\"+str(lo[i]))
        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
        print(gcd(89,6))
        ans=[]
        if -1<n<2:return ans
        for i in range(1,n):
            for j in range(i+1,n+1):#pass
                
##                print(st)
                if i!=j:
                    x=gcd(i,j)
                    print(i,j,x)
##                    print(x)
                    n1=i
                    n2=j
                    if i%x==0==j%x and x>1:
                        n1//=x
                        n2//=x
##                    st=(i,j)
##                    print(st)
                    st=f'{n1}/{n2}'
                    if st not in ans:
                        ans.append(st)
##        ans.sort()
##        print(ans)
##        for i,an in enumerate(ans):
##            ans[i]=f'{an[0]}/{an[1]}'
                        
        return ans

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 []
        a=[]
        ans=[]
        for i in range(1,n):
            for j in range(i+1,n+1):
                if i/j not in a:
                    a.append(i/j)
                    ans.append(str(i)+\"/\"+str(j))
                    
        return ans
                

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
#         if n == 1:
#             return []
        
        results = []
        fractions = []
        for i in range(1, n+1):
            for j in range(1, i+1):
                tmp = j/i
                # if tmp >= 1:
                    # break
                if tmp not in results and tmp < 1:
                    results.append(tmp)
                    fractions.append(\"{}/{}\".format(j, i))
        return fractions   

#         fractions = []
#         decimals = set()
        
#         for i in range(1, n + 1):
#             for x in range (1, i + 1):
#                 if (x % i != 0 and x/i not in decimals):
#                     decimals.add(x/i)
#                     fractions.append(str(x) + \"/\" + str(i))
                    
#         return fractions
    
# a = Solution()
# res = a.simplifiedFractions(4)
# print(res)

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
                


class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def hcfnaive(a,b): 
            if(b==0): 
                return a 
            else: 
                return hcfnaive(b,a%b) 
        ans = []
        for j in range(1,n+1):
            for i in range(1,j):
                igcd = hcfnaive(i,j)
                top,botm = i//igcd,j//igcd
                if top==1 and botm==1:
                    continue
                else:
                    temp = str(top)+\"/\"+str(botm)
                    if temp not in ans:
                        ans.append(temp)
        return ans

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        res = []
        for i in range(1, n):
            for j in range (i + 1, n + 1):
                g = gcd(i, j)
                a, b = i // g, j // g
                s = str(a) + \"/\" + str(b)
                
                if s not in res:
                    res.append(s)
        return res