ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে nums এবং একটি ধনাত্মক পূর্ণসংখ্যা k আছে, আমাদের বের করতে হবে কি এই অ্যারেকে k ক্রমাগত সংখ্যার সেটে ভাগ করা সম্ভব। তাই আমাদের True ফেরত দিতে হবে যদি সম্ভব হয় অন্যথায় False। তাই যদি ইনপুট হয় [1,2,3,3,4,4,5,6] এবং k = 4, তবে আউটপুট হবে true। কারণ, আমরা অ্যারেকে এভাগে ভাগ করতে পারি যেন [1,2,3,4] এবং [3,4,5,6]
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- একটি ম্যাপ m তৈরি করুন, n := nums অ্যারেতে আকার সেট করুন
- nums-এ প্রতিটি উপাদান e জন্য
- m[e] ১ বৃদ্ধি করুন
- cnt := ০
- nums অ্যারে সাজান
- i = 0 থেকে n পর্যন্ত
- x := nums[i]
- যদি m[x – 1] = 0 এবং m[x] > 0
- l := k
- যখন k > 0
- যদি m[x] > 0, তবে m[k] মান ১ হ্রাস করুন, অন্যথায় false ফেরত দিন
- x এবং cnt ১ বৃদ্ধি করুন, এবং k ১ হ্রাস করুন
- k := l
- যদি cnt = n হয় তবে true ফেরত দিন, অন্যথায় false
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#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
