C++ में डबल्ड पेयर्स का ऐरे (Array of Doubled Pairs)

मान लीजिए हमारे पास सम लंबाई का एक पूर्णांक ऐरे A है, अब हमें true कहना है यदि और केवल यदि इसे इस तरह से पुनः क्रमबद्ध करना संभव है कि A[2 * i + 1] = 2 * A[2 * i] प्रत्येक 0 ≤ i < len(A) / 2 के लिए।

उदाहरण के लिए, यदि इनपुट [3,1,3,6] है तो परिणाम false होगा, जबकि [4,-2,2,-4] true लौटाएगा।

समाधान दृष्टिकोण

1. एक मैप m में प्रत्येक तत्व की आवृत्ति स्टोर करें

2. cnt := A का आकार

3. मैप के प्रत्येक कुंजी-मान जोड़े के लिए:

4. यदि कुंजी ≠ 0 और 2*कुंजी मौजूद है, तो न्यूनतम आवृत्ति से जोड़े बनाएं

5. यदि कुंजी = 0, तो सभी जोड़े आंतरिक रूप से बनाएं

6. यदि cnt शून्य हो जाता है तो true, अन्यथा false

C++ कार्यान्वयन

#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(); 
        for(auto it = m.begin(); it != m.end(); it++){ 
            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; 
                } 
            } 
        } 
        return !cnt; 
    } 
}; 

int main(){ 
    vector<int> v1 = {3,1,3,6}; 
    Solution ob; 
    cout << (ob.canReorderDoubled(v1)) << endl; 
    v1 = {4,-2,2,-4}; 
    cout << (ob.canReorderDoubled(v1)); 
    return 0; 
}

इनपुट

[3,1,3,6] [4,-2,2,-4]

आउटपुट

0 1