C++-এ কি একটি লিস্ট k আকারের ক্রমবর্ধমান সাবলিস্টে ভাগ করা সম্ভব তা যাচাই করার প্রোগ্রাম

সমস্যা বিবরণ

একটি সংখ্যা লিস্ট nums এবং একটি সংখ্যা k দেওয়া থাকলে, যাচাই করতে হবে কি লিস্টটি k আকারের সাবলিস্টগুলিতে ভাগ করা সম্ভব যাতে প্রতিটি সাবলিস্টে ক্রমাগত ক্রমবর্ধমান মান থাকে।

উদাহরণ: nums = [4, 3, 2, 4, 5, 6], k = 3 হলে আউটপুট True, কারণ [2,3,4] এবং [4,5,6] এভাবে ভাগ করা যায়।

সমাধানের পদ্ধতি

ম্যাপ (frequency count) এবং গ্রিডি পদ্ধতি ব্যবহার করে:

1. প্রতিটি সংখ্যার ফ্রিকোয়েন্সি গণনা করুন।
2. যতক্ষন ম্যাপ খালি নয়:
   • সর্বনিম্ন মান যেটির আগের মান (value-1) ম্যাপে নেই, সেটি খুঁজুন।
   • সেই মান থেকে value + k - 1 পর্যন্ত সব মান ম্যাপে আছে কিনা চেক করুন।
   • যদি সব থাকে, তবে তাদের ফ্রিকোয়েন্সি ১ করে কমান এবং ০ হলে মুছে দিন।
   • যদি কোনো সময় সম্ভব না হয়, তবে false রিটার্ন করুন।
3. ম্যাপ খালি হলে true রিটার্ন করুন।

C++ কোড উদাহরণ

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

class Solution {
public:
    bool solve(vector nums, int k) {
        map m;
        for (auto& it : nums) m[it]++;
        
        bool ok = true;
        while (m.size() && ok) {
            ok = false;
            for (auto& it : m) {
                if (!m.count(it.first - 1)) {
                    bool flag = true;
                    for (int i = it.first; i <= it.first + k - 1; i++) {
                        if (!m.count(i)) flag = false;
                    }
                    if (flag) {
                        for (int i = it.first; i <= it.first + k - 1; i++) {
                            m[i]--;
                            if (m[i] == 0) m.erase(i);
                        }
                        ok = true;
                        break;
                    }
                }
            }
        }
        return m.empty();
    }
};

int main() {
    vector v = {4, 3, 2, 4, 5, 6};
    Solution ob;
    cout << ob.solve(v, 3);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {4, 3, 2, 4, 5, 6}, k=3

আউটপুট: 1 (True)

জটিলতা

• সময়: O(n log n) — ম্যাপ অপারেশনগুলোর কারণে
• স্থান: O(n)