मान लीजिए रीमा के पास कार्ड्स का एक हाथ है, जिसे पूर्णांकों की एक सरणी के रूप में दिया गया है। अब वह कार्ड्स को समूहों में फेरबदल करना चाहती है ताकि प्रत्येक समूह का आकार W हो, और इसमें W लगातार कार्ड हों। हमें जांचना है कि यह संभव है या नहीं।
तो यदि कार्ड्स [1,2,3,6,2,3,4,7,8] हैं, और W = 3, तो उत्तर true होगा, क्योंकि वह उन्हें [1,2,3],[2,3,4],[6,7,8] की तरह पुनर्व्यवस्थित कर सकती है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक मैप m परिभाषित करें, और हाथ में प्रत्येक तत्व की आवृत्ति को m में संग्रहीत करें
- जब तक हाथ का आकार 0 नहीं है
- prev := 0
- it := m में पहली कुंजी-मान जोड़ी का पॉइंटर
- i को 0 से W - 1 की रेंज में
- जब तक it का मान 0 है, it := अगली जोड़ी की ओर इंगित करें
- यदि i > 0 और it की कुंजी - 1 = prev या i = 0, तो
- it के मान को 1 से घटाएं
- prev := it की कुंजी
- अन्यथा false लौटाएं
- it := अगली जोड़ी की ओर इंगित करें
- n := n - W
- true लौटाएं।
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int W) {
map <int, int> m;
int n = hand.size();
if(n % W != 0) return false;
for(int i = 0; i < n; i++){
m[hand[i]]++;
}
while(n){
map <int, int> :: iterator it = m.begin();
int prev = 0;
for(int i = 0; i < W; i++){
while(it->second == 0) it++;
if((i > 0 && it->first - 1 == prev) || i == 0){
it->second--;
prev = it->first;
}else{
return false;
}
it++;
}
n -= W;
}
return true;
}
};
main(){
vector<int> v = {1,2,3,6,2,3,4,7,8};
Solution ob;
cout << (ob.isNStraightHand(v, 3));
}
इनपुट
[1,2,3,6,2,3,4,7,8] 3
आउटपुट
1
