ধরুন আমাদের কাছে জোড় দৈর্ঘ্যের পূর্ণসংখ্যা A এর একটি অ্যারে আছে, এখন আমাদের সত্য বলতে হবে যদি এবং শুধুমাত্র যদি এটিকে এমনভাবে পুনর্বিন্যাস করা সম্ভব হয় যাতে A[2 * i + 1] =2 * A[2 * i] প্রতি 0 <=i
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
একটি মানচিত্র m, n :=A এর আকার তৈরি করুন, A-তে প্রতিটি উপাদানের ফ্রিকোয়েন্সি m এ সঞ্চয় করুন
cnt :=A
মানচিত্রে প্রতিটি কী-মানের জোড়া kv-এর জন্য
যদি m[kv-এর কী]> 0 হয়, তাহলে
যদি m[kv-এর কী] 0 না হয় এবং m[2* kv-এর কী]> 0
x :=m[kv-এর কী] এবং kv-এর m[2* কী]
cnt :=cnt – (x * 2)
x
x
অন্যথায় যখন kv =0 এর কী, তারপর
cnt :=cnt – m[kv এর কী]
m[kv এর কী] :=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
