ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে এবং একটি ধনাত্মক পূর্ণসংখ্যা k আছে, আমাদের খুঁজে বের করতে হবে এই অ্যারেটিকে k ধারাবাহিক সংখ্যার সেটে ভাগ করা সম্ভব কিনা। তাই যদি সম্ভব হয় তাহলে আমাদের True ফেরত দিতে হবে অন্যথায় False ফেরত দিতে হবে। সুতরাং ইনপুট যদি [1,2,3,3,4,4,5,6] এবং k =4 এর মত হয় তবে আউটপুট সত্য হবে। এর কারণ হল, আমরা অ্যারেটিকে এভাবে ভাগ করতে পারি যে [1,2,3,4] এবং [3,4,5,6]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি মানচিত্র m তৈরি করুন, n :=সংখ্যা বিন্যাসের আকার সেট করুন
- প্রতিটি উপাদানের জন্য e সংখ্যায়
- m[e] 1 দ্বারা বাড়ান
- cnt :=0
- সংখ্যা অ্যারে সাজান
- আমি 0 থেকে n
- পরিসরে
- x :=সংখ্যা[i]
- যদি m[x – 1] =0 এবং m[x]> 0
- l :=k
- যখন k> 0
- যদি m[x]> 0 হয়, তাহলে m[k] এর মান 1 কমিয়ে দিন, অন্যথায় মিথ্যা ফেরত দিন
- x এবং cnt 1 দ্বারা বাড়ান এবং k কে 1 দ্বারা হ্রাস করুন
- k :=l
- সত্য ফেরত যখন cnt =n, অন্যথায় মিথ্যা
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
map <int, int> m;
int n = nums.size();
for(int i = 0; i < n; i++){
m[nums[i]]++;
}
int cnt = 0;
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i++){
int x = nums[i];
if(m[x - 1] == 0 && m[x] > 0){
int l = k;
while(k>0){
if(m[x] > 0){
m[x]--;
} else return false;
x++;
k--;
cnt++;
}
k = l;
}
}
return cnt == n;
}
};
main(){
vector<int> v = {1,2,3,3,4,4,5,6};
Solution ob;
cout << (ob.isPossibleDivide(v, 4));
} ইনপুট
[1,2,3,3,4,4,5,6] 4
আউটপুট
1
