Most Intuitive Binary Search Solution
Intuition\nIf you sort the original array, it is optimal to apply the operations on one subarray such that all the elements of that subarray become equal.\n\nYo
# Intuition\nIf you sort the original array, it is optimal to apply the operations on one subarray such that all the elements of that subarray become equal.\n\nYou can use binary search to find the longest subarray where we can make the elements equal in at most k operations.\n\nAlso to calculate whether all the elements of a subarray can be converted a single element within k operations, we need to find the optimal element to be converted into. \n\nFor every subarray this optimal element will be the median , because sum of deviation of all elements from the median is minimal as compared to than that of any other measure of central tendency. \n\nSo, for all the subarrays of a particular length among the array, Find whether there is any subarray whose elements can be reduced to single element within k operations.\n\nIf it possible , then strive for more length .\n\n# Complexity\n- Time complexity:\nO(nlog(n))\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n   int maxFrequencyScore(vector<int> &a, long long k)\n{\n    long long n = a.size();\n\n    sort(a.begin(), a.end());\n\n    vector<long long> pf(n + 1, 0);\n    for (long long i = 1; i <= n; i++)\n    {\n        pf[i] = pf[i - 1] + a[i - 1];\n    }\n\n    auto pred = [&](long long m)\n    {\n        bool possible = false;\n        for (long long i = m; i <= n; i++)\n        {\n            if (m % 2 == 1)\n            {\n                long long deviation = 0;\n\n                long long ind = (i - (m / 2));\n                long long median = a[ind - 1];\n                long long s1 = (pf[ind] - pf[i - m]);\n\n                deviation += ((median * ((m / 2) + 1)) - s1);\n\n                long long s2 = (pf[i] - pf[ind]);\n                deviation += (s2 - (median * (m / 2)));\n\n                if (deviation <= k)\n                {\n                    possible = 1;\n                }\n            }\n            else\n            {\n                long long ind1 = (i - (m / 2));\n                long long median1 = (a[ind1 - 1]);\n                long long deviation1 = 0;\n\n                deviation1 += ((median1 * (m / 2)) - (pf[ind1] - pf[i - m]));\n                deviation1 += ((pf[i] - pf[ind1]) - (median1 * (m / 2)));\n\n                if (deviation1 <= k)\n                {\n                    possible = 1;\n                }\n\n                long long ind2 = (i - (m / 2) + 1);\n                long long median2 = (a[ind2 - 1]);\n                long long deviation2 = 0;\n\n                deviation2 += ((pf[i] - pf[ind2 - 1]) - (median2 * (m / 2)));\n                deviation2 += ((median2 * (m / 2)) - (pf[ind2 - 1] - pf[i - m]));\n\n                if (deviation2 <= k)\n                {\n                    possible = 1;\n                }\n            }\n\n            if (possible)\n            {\n                break;\n            }\n        }\n\n        return possible;\n    };\n\n    long long l = 0, r = n + 1;\n    while (r - l > 1)\n    {\n        long long m = (l + r) / 2;\n        pred(m) ? (l = m) : (r = m);\n    }\n\n    return l;\n}\n};\n```
['Binary Search', 'Prefix Sum', 'Probability and Statistics', 'C++']