C++-তে অ্যারে আকার অর্ধেক করতে_MINIMUM সেট আকার নির্ণয়

সমস্যা বিবরণ

একটি INTEGER অ্যারে arr দেওয়া আছে। আমরা একটি INTEGER SET বেছে নিতে পারি এবং সেই সেটের সব INTEGER-গুলোর সব OCURRENCE অ্যারে থেকে মুছে ফেলতে পারি। লক্ষ্য হলো ন্যূনতম আকারের সেট বের করা যাতে অ্যারে এর অন্তত অর্ধেক INTEGER মুছে যায়।

উদাহরণ

Input:  arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2

ব্যাখ্যা: অ্যারের আকার = 10। অর্ধেক = 5।
যদি সেট {3, 7} বেছে নিই: 3 (৪ বার) এবং 7 (১ বার) = ৫টি এলিমেন্ট মুছে যায়। বাকি থাকে [5,5,5,2,2] (আকার ৫)।
অন্য বৈধ সেট: {3,5}, {3,2}, {5,2}।
{2,7} অবৈধ কারণ তখন ৩টি মात्र মুছে যায়, বাকি থাকে ৭টি (>5)।

সমাধানের অ্যালগরিদম (Greedy Approach)

1. ফ্রিকোয়েন্সি গণনা: প্রতিটি অনন্য INTEGER-র ফ্রিকোয়েন্সি (কতবার এসেছে) একটি HASH MAP-এ সংরক্ষণ করুন।
2. ফ্রিকোয়েন্সি সাজান: সমস্ত ফ্রিকোয়েন্সি মানগুলো একটি VECTOR-এ নিয়ে DESCENDING ORDER-এ সাজান (সর্বোচ্চ ফ্রিকোয়েন্সি আগে)।
3. লালচী বেছে নেওয়া (Greedy Selection): সর্বোচ্চ ফ্রিকোয়েন্সি वालা INTEGER-গুলো এক এক করে সেটে যোগ করুন যতক্ষণ না মুছে যাওয়া INTEGER-র সংখ্যা অ্যারে আকারের অর্ধেক বা তার বেশি হয়।
4. ফলাফল: সেটে কতটি INTEGER যোগ করা লাগলো, সেটিই উত্তর।

সময় ও জটিলতা বিশ্লেষণ

C++ বাস্তবায়ন (Solution Class)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        // 1. ফ্রিকোয়েন্সি গণনা
        unordered_map<int, int> freq;
        for (int num : arr) {
            freq[num]++;
        }

        // 2. ফ্রিকোয়েন্সি ভেক্টরে সংগ্রহ ও ডিসেন্ডিং সর্ট
        vector<int> frequencies;
        frequencies.reserve(freq.size());
        for (auto& [num, count] : freq) {
            frequencies.push_back(count);
        }
        sort(frequencies.rbegin(), frequencies.rend()); // descending

        // 3. Greedy selection
        int n = arr.size();
        int removed = 0;
        int setSize = 0;
        for (int count : frequencies) {
            if (removed >= n / 2) break;
            removed += count;
            setSize++;
        }
        return setSize;
    }
};

// টেস্ট ড্রাইভার
int main() {
    Solution sol;
    vector<int> arr = {3,3,3,3,5,5,5,2,2,7};
    cout << "Minimum set size: " << sol.minSetSize(arr) << endl; // Output: 2
    return 0;
}

কোড ব্যাখ্যা

• unordered_map — O(1) গড় সময়ে ফ্রিকোয়েন্সি গণনায় ব্যবহৃত।
• sort(frequencies.rbegin(), frequencies.rend()) — রিভার্স ইটারেটর ব্যবহার করে ডিসেন্ডিং অর্ডারে সাজানো।
• removed >= n / 2 — শর্ত পূরণ হলে লুপ ব্রেক করে দিচ্ছে।
• frequencies.reserve(freq.size()) — মেমরি রি-অ্যালোকেশন এড়াতে রিজার্ভ করা হয়েছে।

LeetCode সমস্যা রেফারেন্স

এটি LeetCode 1338. Reduce Array Size to The Half সমস্যার সমাধান। অনুশীলনের জন্য LeetCode-এ জমা দিন।

অতিরিক্ত টেস্ট কেস