একটি ধনাত্মক পূর্ণসংখ্যার অ্যারে nums দেওয়া আছে। আমাদের সবচোটে প্রিফিক্স দৈর্ঘ্য বের করতে হবে যাতে সেখান থেকে ঠিক একটি এলিমেন্ট মুছে দিলে বাকি সব সংখ্যার ফ্রিকোয়েন্সি সমান হয়ে যায়। যদি মুছে দিলে কিছুই না থাকে, তবে সেটিও বৈধ (ফ্রিকোয়েন্সি ০)।
উদাহরণ
ইনপুট: [3,3,2,2,6,4,4,6] → আউটপুট: 7
ব্যাখ্যা: ইন্ডেক্স ৪-এর ৬ মুছে দিলে সাবঅ্যারে [3,3,2,2,4,4] হবে যেখানে সব সংখ্যা ২ বার করে আসছে।
সমাধানের ধাপসমূহ
cnt[x]= সংখ্যাx-এর ফ্রিকোয়েন্সি।freq[f]= ফ্রিকোয়েন্সিfপাওয়া সংখ্যাগুলোর কাউন্ট।- প্রতিটি এলিমেন্ট প্রসেস করার সময়
maxFreqআপডেট করুন। - ৩টি বৈধ কেস চেক করুন:
maxFreq * freq[maxFreq] == i(সব সংখ্যার ফ্রিকোয়েন্সি সমান, শেষটা বাদ দিলে)(maxFreq-1) * (freq[maxFreq-1] + 1) == i(একটা সংখ্যার ফ্রিকোয়েন্সি বেশি, সেটা কমালে)maxFreq == 1(সব সংখ্যা একবারই আসছে)
- বৈধ হলে
res = i + 1আপডেট করুন।
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
int maxf = 0, res = 0;
map<int, int> cnt, freq;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
cnt[x]++;
int f = cnt[x];
freq[f]++;
freq[f - 1]--;
maxf = max(maxf, f);
if (maxf * freq[maxf] == i ||
(maxf - 1) * (freq[maxf - 1] + 1) == i ||
maxf == 1) {
res = i + 1;
}
}
return res;
}
};
int main() {
Solution ob;
vector<int> v = {3,3,2,2,6,4,4,6};
cout << (ob.maxEqualFreq(v));
}
ইনপুট
{3,3,2,2,6,4,4,6}
আউটপুট
7
