मान लीजिए कि हमारे पास कार्डों का एक डेक है, प्रत्येक कार्ड पर एक पूर्णांक लिखा है। हमें यह जांचना होगा कि क्या हम X>=2 को इस प्रकार चुन सकते हैं कि पूरे डेक को कार्डों के 1 या अधिक समूहों में विभाजित करना संभव हो, जहां निम्नलिखित शर्त पूरी होती है:प्रत्येक समूह में बिल्कुल X संख्या वाले कार्ड होते हैं। प्रत्येक समूह के सभी कार्डों की संख्या समान होती है।
इसलिए, यदि इनपुट डेक =[1,2,3,4,4,3,2,1] की तरह है, तो आउटपुट ट्रू होगा, संभव के रूप में विभाजन [1,1], [2,2] हैं, [3,3], [4,4]।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक नक्शा एमपी परिभाषित करें
- डेक में सभी x के लिए
- (mp[x] 1 से बढ़ाएं)
- एमपी में सभी की-वैल्यू पेयर x के लिए
- उत्तर :=gcd of (उत्तर और x का मान)
- सही लौटें जब उत्तर> 1, अन्यथा गलत
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map<int, int> mp;
int ans;
for (auto x : deck)
mp[x]++;
for (auto x : mp)
ans = __gcd(ans, x.second);
return (ans > 1);
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,4,3,2,1};
cout << (ob.hasGroupsSizeX(v));
} इनपुट
{1,2,3,4,4,3,2,1} आउटपुट
1