<p>Given an integer <code>n</code>, return <em>a list of all <strong>simplified</strong> fractions between </em><code>0</code><em> and </em><code>1</code><em> (exclusive) such that the denominator is less-than-or-equal-to </em><code>n</code>. You can return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> [&quot;1/2&quot;]
<strong>Explanation:</strong> &quot;1/2&quot; is the only unique fraction with a denominator less-than-or-equal-to 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> [&quot;1/2&quot;,&quot;1/3&quot;,&quot;2/3&quot;]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> [&quot;1/2&quot;,&quot;1/3&quot;,&quot;1/4&quot;,&quot;2/3&quot;,&quot;3/4&quot;]
<strong>Explanation:</strong> &quot;2/4&quot; is not a simplified fraction because it can be simplified to &quot;1/2&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
</ul>

class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ret;
        string str;
        int a{2}, b{4}, hcf{1};

        for(int i = 1; i<n ; i++){
            for(int j = i+1; j<=n; j++){
                str = to_string(i) +"/" + to_string(j);
                if(i== 1){
                    str = to_string(i) +"/" + to_string(j); 
                    ret.push_back(str);
                }
                else{
                    hcf = gcd(i,j);
                    a = i/hcf;
                    b = j/hcf;
                    str = to_string(a) +"/" + to_string(b);

                    if(count(ret.begin(), ret.end(), str) == 0){ 
                        ret.push_back(str);
                    }
                }
            }
        }

        return ret;        
    }

    static int gcd(int a,int b){
        int ans=1;
        for(int i=a;i>=2;i--){
            if((a%i==0) && (b%i==0)){
                ans=i;
                break;
            }
        }
        return ans;
    }
};
25900