मान लीजिए हमारे पास एक इंटीजर n है, हमें 0 और 1 (एक्सक्लूसिव) के बीच के सभी सरलीकृत भिन्नों की सूची ढूंढनी है जैसे कि हर <= n। यहाँ भिन्न किसी भी क्रम में हो सकते हैं।
इसलिए, यदि इनपुट है n = 4, तो आउटपुट होगा ["1/2","1/3","1/4","2/3","3/4"] क्योंकि "2/4" एक सरलीकृत भिन्न नहीं है क्योंकि इसे "1/2" में सरल किया जा सकता है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक ऐरे ret परिभाषित करें
i := 2 से शुरू करें, जब i <= n, i बढ़ाते हुए, करें -
j := 1 से शुरू करें, जब j < i, j बढ़ाते हुए, करें -
c := i और j का gcd
a := j / c
b := i / c
(a को स्ट्रिंग के रूप में + "/" + b को स्ट्रिंग के रूप में) को ret के अंत में डालें
ret में मौजूद सभी यूनिक एलिमेंट्स का ऐरे लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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()); } }; main(){ Solution ob; print_vector(ob.simplifiedFractions(4)); }इनपुट
4
आउटपुट
[1/2, 1/3, 1/4, 2/3, 3/4, ]
