Easy C++ with explanation|| binary search with sliding window
Intuition\nwe have to find a element in the array which is in the mid of the smallest and the largest element of array and is present in the array so we will fi
# Intuition\nwe have to find a element in the array which is in the mid of the smallest and the largest element of array and is present in the array so we will find the median.\n\nMedian will benefit the most as it will require least number of operations to make neighbouring elements equal to median.\n\nNow we can easily check for the neighbouring elements for median the number of operations which will cost to make them equal.\n\nNEED OF PREFIX SUM ARRAY\ntime complexity will be n*log(max(nums.size())). let say it nlog(k).\nnow we have to calculate the cost in o(1) time to find the answer the the time frame as if we will take another O(n) time for that the we will get "TLE".\n\n# Approach\nstep 1) sort thee array to use binary search and to find the median element.\nstep 2) find prefix sum.\nstep 3) apply binary search from index 0 to n (not n-1 where n is size of array because we have to calculate the size of subsets).\nstep 4) for all subsets of all size from 2 to n check if it is possibl to get all elements same in atmost k operations.\nstep 5) retur max size that is indeed the max frequency\n\nPlease Upvote.\n# Complexity\n- Time complexity:\ntime complexity will be n*log(max(nums.size())). let say it nlog(k).\n\n- Space complexity:\nO(n);\n\n# Code\n```\n#define ll long long int\nclass Solution {\npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        int n = nums.size() , ans=1;\n\n        sort(nums.begin(), nums.end());\n        vector<ll> prefixSum(n,0);\n        prefixSum[0] = nums[0];\n\n        for(int i=1; i<n; i++){\n            prefixSum[i] = prefixSum[i-1] + nums[i];\n        }\n\n        int l=0,r=n;\n        while(l <= r){\n            int mid = (l+r)/2;\n            int lenToTry = mid;\n            bool isGood = 0;\n\n            for(int j=0,i=0; j<n; j++){\n                if(j-i+1 == lenToTry){\n                    int medianIndex = (i+j)/2;\n                    ll medianElement = nums[medianIndex];\n                    ll leftSum = prefixSum[medianIndex] - prefixSum[i] + nums[i];\n                    ll countLeftElement = medianIndex-i+1; \n                    ll rightSum = prefixSum[j] - prefixSum[medianIndex] + nums[medianIndex];\n                    ll countRightElement = j-medianIndex+1;\n\n                    ll cost = (medianElement*countLeftElement - leftSum) + (rightSum - countRightElement*medianElement);\n\n                    if(cost <= k){\n                        isGood = 1; \n                        break;\n                    }  \n                    i++; \n                }\n            }\n            if(isGood){\n                ans = mid;\n                l = mid+1;\n            }\n            else{\n                r = mid-1;\n            }\n        }\n        return ans;\n    }\n};\n//please upvote\n```
['C++']