मान लीजिए कि हमारे पास सम लंबाई के साथ पूर्णांक A की एक सरणी है, अब हमें सच कहना होगा यदि और केवल यदि इसे इस तरह से पुन:व्यवस्थित करना संभव हो कि A[2 * i + 1] =2 * A[2 * i] प्रत्येक 0 <=i <लेन (ए) / 2 के लिए। तो यदि इनपुट [3,1,3,6] जैसा है तो परिणाम गलत होगा, जहां [4,-2,2,-4], सच लौटेगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक नक्शा बनाएं एम, एन:=ए का आकार, ए में प्रत्येक तत्व की आवृत्ति को मानचित्र एम में संग्रहीत करें
-
cnt :=A का आकार
-
मानचित्र में प्रत्येक कुंजी-मान युग्म kv के लिए
-
अगर एम [केवी की कुंजी]> 0, तो
-
अगर m[kv की key] 0 नहीं है और m[2* key of kv]> 0
-
x :=मिनट का m[kv की कुंजी] और m[2* kv की कुंजी]
-
सीएनटी:=सीएनटी - (एक्स * 2)
-
x द्वारा m[2 * kv की कुंजी] घटाएं
-
मी [केवी की कुंजी] को x से कम करें
-
-
अन्यथा जब kv =0 की कुंजी हो, तब
-
सीएनटी:=सीएनटी - एम [केवी की कुंजी]
-
एम [केवी की कुंजी] :=0
-
-
-
-
जब सीएनटी शून्य न हो, तो झूठी वापसी करें, अन्यथा सत्य
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canReorderDoubled(vector<int>& A) {
map <int, int> m;
int n = A.size();
for(int i = 0; i < n; i++){
m[A[i]]++;
}
int cnt = A.size();
map <int, int> :: iterator it = m.begin();
while(it != m.end()){
if(m[it->first] > 0){
if(it->first != 0 && m[it->first * 2] > 0){
int x = min(m[it->first], m[it->first * 2]);
cnt -= (x * 2);
m[it->first * 2] -= x;
m[it->first] -= x;
}else if(it->first == 0){
cnt -= m[it->first];
m[it->first] = 0;
}
}
it++;
}
return !cnt;
}
};
main(){
vector<int> v1 = {3,1,3,6};
Solution ob;
cout << (ob.canReorderDoubled(v1)) << endl;
v1 = {4,-2,2,-4};
cout << (ob.canReorderDoubled(v1));
} इनपुट
[3,1,3,6] [4,-2,2,-4]
आउटपुट
0 1
