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