Use Median || BS || Prefix Sum || AC ✅
\n# Code\n\nclass Solution {\npublic:\n    \n    #define ll long long   \n    bool solve(int start , int end , int mid , vector<ll> &pre , ll k , vector<int> &n
\n# Code\n```\nclass Solution {\npublic:\n    \n    #define ll long long   \n    bool solve(int start , int end , int mid , vector<ll> &pre , ll k , vector<int> &nums){\n         \n        if(mid<0 || mid>=nums.size())return false; \n       \n        ll ans = k + 1;\n        \n        ll val = nums[mid]; \n        \n        ll pre1 = start==0 ? pre[mid] : pre[mid] - pre[start-1];  \n        ll pre2 = mid==0 ? pre[end] : pre[end] - pre[mid-1]; \n        \n        ll a = abs(1ll*(mid-start+1)*val - pre1); \n        ll b = abs(1ll*(end - mid + 1)*val - pre2);  \n        \n        ans = min(ans , a + b); \n        return ans<=k; \n    }\n    \n    bool fun(int size , vector<int> &nums , ll k , vector<ll> &pre){\n        \n        int n = nums.size(); \n        ll ans = k + 1; \n        \n       for(int i =  0 ; i < n ; i++){\n                \n                int start = i ; \n                int end = start + size - 1;   \n                if(end>=n)break; \n                \n                int mid1 = start + (size)/2;   \n                int mid2 = mid1-1; \n                \n                bool ok1 = solve(start , end , mid1 , pre , k , nums );\n                bool ok2 = solve(start , end , mid2 , pre , k , nums);\n                if(ok1 || ok2)return true; \n                \n        }\n            \n        return false; \n    } \n    \n    \n    int maxFrequencyScore(vector<int>& nums, long long k) {\n         \n        int n = nums.size();  \n        sort(nums.begin() , nums.end()); \n        \n        vector<ll> pre(n , nums[0]); \n        for(int i = 1 ; i < n; i++)pre[i] = pre[i-1] + nums[i]; \n        \n        int l = 1 , h = n , ans = 1; \n        \n        while(l<=h){\n            \n            int mid = l + (h-l)/2; \n            bool ok = fun(mid , nums , k , pre);  \n            if(ok)ans = mid , l = mid+1; \n            else h = mid-1; \n        }\n        \n        return ans;\n    }\n};\n```
['Math', 'Binary Search', 'Sliding Window', 'Prefix Sum', 'C++']