C++ में दोगुने जोड़े की सरणी

मान लीजिए कि हमारे पास सम लंबाई के साथ पूर्णांक 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