ধরুন আমাদের একটি অ্যারে সংখ্যা আছে যা আরোহী ক্রমে সাজানো হয়েছে। আমাদের সত্যে ফিরে আসতে হবে যদি এবং শুধুমাত্র যদি আমরা এটিকে 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