C++-এ সরলীকৃত ভগ্নাংশ বের করা

একটি ইন্টিজার n দেওয়া আছে। ০ থেকে ১ এর মধ্যে (এক্সক্লুসিভ) সকল সরলীকৃত ভগ্নাংশ বের করতে হবে যাদের হর n এর চেয়ে ছোট বা সমান। ভগ্নাংশগুলো যেকোনো ক্রমে হতে পারে।

ইনপুট: n = 4 → আউটপুট: ["1/2","1/3","1/4","2/3","3/4"] ("2/4" সরলীকৃত নয়)

সমাধানের ধাপগুলো:

• হর i = 2 থেকে n পর্যন্ত লুপ

• অংশ j = 1 থেকে i-1 পর্যন্ত লুপ

• gcd(i,j) বের করব

• a = j/gcd, b = i/gcd হিসেবে ভগ্নাংশ স্ট্রিং বানাব

• সেট দিয়ে ডুপ্লিকেট রিমুভ করব

উদাহরণ

নিচের কোডটি দেখুন −

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<string> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> ret;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                int c = __gcd(i, j);
                int a = j / c;
                int b = i / c;
                ret.push_back(to_string(a) + "/" + to_string(b));
            }
        }
        set<string> s(ret.begin(), ret.end());
        return vector<string>(s.begin(), s.end());
    }
};

int main() {
    Solution ob;
    print_vector(ob.simplifiedFractions(4));
}

ইনপুট

4

আউটপুট

[1/2, 1/3, 1/4, 2/3, 3/4, ]