মান লেযিয়ে একটি পূর্ণসংখ্যা অ্যারে 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।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
একটি ম্যাপ m তৈরি করুন, n := A.size(), A-এর প্রতিটি এলিমেন্টের ফ্রিকোয়েন্সি m-এ স্ট্রোর করুন
cnt := A.size()
ম্যাপের প্রতিটি key-value pair kv-এর জন্য
যদি m[kv.first] > 0 হয়, তবে
যদি kv.first != 0 এবং m[2 * kv.first] > 0 হয়, তবে
x := min(m[kv.first], m[2 * kv.first])
cnt := cnt - (x * 2)
m[2 * kv.first] := m[2 * kv.first] - x
m[kv.first] := m[kv.first] - x
অন্যথায় যদি kv.first == 0 হয়, তবে
cnt := cnt - m[kv.first]
m[kv.first] := 0
যদি cnt ≠ 0 হয় false রিটার্ন করুন, অন্যথায় true
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#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
