C++| Simplest approach... beats 100%
Miami here with another 100% beating code: \n\n\nedit: just for the sake of completeness, I added binary search approach as well but I find that one inefficient
Miami here with another 100% beating code: \n![Capture.PNG](https://assets.leetcode.com/users/images/b546c4f4-c735-47a3-8288-78aabdd69cf9_1702790893.1433342.png)\n\nedit: just for the sake of completeness, I added binary search approach as well but I find that one inefficient \n# 1. Sliding Window\n# Intuition\nHere we can either increment or decrement any element of array, in principle whenever we have to make a range of elements equal to a single value by decreasing and increasing, that element needs to be the median of sorted order of those elements  to get optimal result, after understanding this the problem just becomes a simple sliding window problem where we will increment  right pointer if result are valid otherwise increment left pointer. sliding window by itself has time complexity of O(2*n)....\n\n# Approach\nSo here we would first need to calculate `prefix` sum array that will store prefix sum till index i...this will help us validating range in $$O(1)$$ time \nnow, define a boolean function `checker` that will return true if our answer is valid for range and otherwise false\nto do so, we will try to make all elements in a range `l` to `r` equal to the mid point `(l+r)/2`, the required cost to do so will be: \n\t`((sum of element greater than nums[m])-(number of elements)*nums[m]` + `(number of elements less than nums[m])*nums[m]-(sum of elements less than nums[m]`\nsum of element part would be: \t\n\t`prefix[r]-prefix[m]-(prefix[m]-prefix[l-1]`\nand the number of element*nums[i] part would be \n\t`nums[m]*(m-l+1)-nums[m](r-m)`\nthese above expression came after simplifying the formula given above \nwe need to check for this cost to be less than or equal to k\nnow we just need to implement simple sliding window ///\n\n# Complexity\n- Time complexity:\n$$O(n logn)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\n    bool checker(vector<int>& nums, vector<long long>&prefix, long long l, long long r, long long k)\n    {\n        long long m=(l+r)/2;\n// prefix[r]-prefix[m]-(prefix[m]-prefix[l-1]) but l-1 is invalid in case of 0\n        long long desired=prefix[r]-2*prefix[m]+(l>0? prefix[l-1]: 0);\n        long long req=nums[m]*(2*m-r-l+1);\n        long long ans=desired+req;\n        return ans<=k;\n    }\npublic:\n    Solution(){\n        ios::sync_with_stdio(0); cin.tie(0); cin.tie(0);\n    }\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        sort(nums.begin(), nums.end());\n        int n=nums.size();\n        long long sum{};\n// calculating prefix sum\n        vector<long long> prefix;\n        for(int i=0; i<n; i++)\n            sum+=nums[i], prefix.push_back(sum);\n        int max=0;\n        int r=0, l=0;\n// sliding window magic\n        while(r<nums.size())\n// if vaild try more elements\n            if(checker(nums, prefix, l, r, k))\n            max=std::max(max, r-l+1), r++;\n// else reduce elements\n            else l++;\n        return max;\n    }\n};\n```\n\n# 2. Binary Search\nAlright this one is, for most of the part just like the last approach, we will use same `checker` function here.....\nThe difference will be that instead of using a single sliding window, we can actually use binary search at each element to get the rightmost value till which our answer would be valid\nBinary search has time complexity $$O(log n)$$ so with `n` operation total time complexity would be $$O(n log n)$$ which is safe but slightly inefficient compared to sliding window\n\n# Complexity\n- Time complexity:\n$$O(n logn)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code: \n```\nclass Solution {\n    bool checker(vector<int>& nums, vector<long long>&prefix, long long l, long long r, long long k)\n    {\n        long long m=(l+r)/2;\n        long long ele=nums[m];\n        // element less than m\n        long long smaller=prefix[m]-(l>0? prefix[l-1]: 0);\n        long long ans=(ele*(m-l+1))-smaller;\n        // elemet greater than m\n        long long larger=prefix[r]-prefix[m];\n        ans+=larger-ele*(r-m);\n        return ans<=k;\n    }\npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        sort(nums.begin(), nums.end());\n        int n=nums.size();\n        long long sum{};\n        vector<long long> prefix;\n        for(int i=0; i<n; i++)\n            sum+=nums[i], prefix.push_back(sum);\n        int max=0;\n        for(int i=0; i<n; i++)\n        {\n            int hi=n-1, lo=i, ans=-1;\n            while(hi>=lo)\n            {\n                int r=(hi+lo)/2;\n                if(checker(nums, prefix, i, r, k))\n                    ans=r, lo=r+1;\n                else hi=r-1;\n            }\n            if(ans!=-1)\n                max=std::max(max, ans-i+1);\n        }\n        return max;\n    }\n};\n```
['C++']