C++ में अधिकतम समान आवृत्ति (Maximum Equal Frequency)

समस्या विवरण

धनात्मक पूर्णांकों की एक सरणी nums दी गई है। सबसे लंबे प्रीफिक्स (prefix) की लंबाई ज्ञात करनी है जिससे ठीक एक तत्व हटाने के बाद, शेष सभी संख्याओं की आवृत्ति (frequency) समान हो जाए। यदि हटाने के बाद कोई तत्व न बचे, तो भी मान्य माना जाता है (आवृत्ति 0)।

उदाहरण

इनपुट

[3,3,2,2,6,4,4,6]

आउटपुट

व्याख्या: सूचकांक 4 पर 6 को हटाने पर: [3,3,2,2,4,4,6] - सभी संख्याएं 2 बार आती हैं।

समाधान दृष्टिकोण (आवृत्ति ट्रैकिंग)

प्रत्येक तत्व जोड़ते समय दो मैप बनाए रखें:

cnt[x]: तत्व x की वर्तमान आवृत्ति
freq[f]: आवृत्ति f वाले तत्वों की संख्या

प्रीफिक्स लंबाई i+1 वैध है यदि:

maxFreq * freq[maxFreq] == i (एक तत्व की आवृत्ति maxFreq+1 है, बाकी maxFreq)
(maxFreq-1) * (freq[maxFreq-1]+1) == i (एक तत्व की आवृत्ति 1 है, बाकी maxFreq)
maxFreq == 1 (सभी तत्व अद्वितीय हैं)

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        int maxFreq = 0, res = 0;
        unordered_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]--;
            maxFreq = max(maxFreq, f);
            
            if (maxFreq * freq[maxFreq] == i ||
                (maxFreq - 1) * (freq[maxFreq - 1] + 1) == i ||
                maxFreq == 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);
    return 0;
}