Prefix Sum + Binary Search Solution
\n# Approach\n1) Sorting the Array: Start by sorting the array. This allows us to use prefix sums and sliding windows effectively.\n\n2) Prefix Sum Array: Creat
\n# Approach\n1) Sorting the Array: Start by sorting the array. This allows us to use prefix sums and sliding windows effectively.\n\n2) Prefix Sum Array: Create a prefix sum array to quickly calculate the sum of any subarray.\n\n3) Binary Search: Use binary search to find the maximum possible frequency. The search range will be between 1 and the length of the array.\n\n4) Sliding Window: For each possible frequency (length of subarray), use a sliding window to check if there exists a subarray where the cost to make all elements equal is within the given limit \uD835\uDC58. Calculate the cost using the prefix sum array.\n\n5) Cost Calculation: For each subarray, calculate the cost to make all elements equal to the median of the subarray. This is efficient because making elements equal to the median minimizes the cost.\n\n6) Update the Result: If a valid subarray is found for a given frequency, update the result and continue searching for a higher frequency. If not, adjust the binary search range accordingly.\n\n# Complexity\n- Time complexity : O(nlogn)\n\n- Space complexity:O(n)\n\n# Code\n```\n#define ll long long\nclass Solution {\npublic:\n\n    ll solve(int l,int r,vector<int>& nums, vector<ll> &ps){\n        ll mid=(l+r)/2;\n        ll leftcost=(nums[mid]*(mid-l+1))-(ps[mid]-ps[l]+nums[l]);\n        ll rightcost=(ps[r]-ps[mid]+nums[mid])-(nums[mid]*(r-mid+1));\n        return leftcost+rightcost;\n    }\n\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        int n=nums.size();\n        if(n==1){\n            return 1;\n        }\n        sort(nums.begin(),nums.end());\n        vector<ll> ps(n,0);\n        ps[0]=nums[0];\n        for(int i=1;i<n;i++){\n            ps[i]=ps[i-1]+nums[i];\n        }\n\n        int low=0, high=nums.size();\n        int ans=1;\n        while(low<=high){\n            int mid=(low+high)/2;\n            int l=0,r=mid-1;\n            bool isOk=false;\n            while(l<=n-mid){\n                ll cost=solve(l,r,nums,ps);\n                if(cost<=k){\n                    isOk=true;\n                    break;\n                }\n                l++;\n                r++;\n            }\n\n            if(isOk){\n                low=mid+1;\n                ans = mid;\n            }else{\n                high=mid-1;\n            }\n        }\n\n        return ans;\n\n    }\n};\n```
['C++']