✅✅Prefix Sum || Binary Search || C++ || Simple Solution with Explanation✅✅
Intuition\n Describe your first thoughts on how to solve this problem. \nPrecomputation, efficient centered group cost computation, and binary search help to so
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nPrecomputation, efficient centered group cost computation, and binary search help to solving the problem.\n\n# Approach\n1. Pre-compute a prefix sum array preSum from the input nums array. This allows us to quickly compute sum of any subarray in O(1) time.\n\n2. The logic is in check() function which tries to fit as many groups as possible under the given constraint k. It considers groups of consecutive numbers from nums array, centered around midpoints. For odd sized groups it takes one midpoint, for even sized it takes two midpoints.\n\n3. For each group, it efficiently computes the cost using precomputed preSum and checks if total cost is <= k.\n\n4. Binary search is used over the size of groups  trying to maximize the group size, while satisfying the cost constraint.\n\n# Complexity\n- Time complexity : O(N*logN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity : O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution\n{\npublic:\n    long long sum(int i, int j, const vector<long long> &preSum)\n    {\n        if (i == 0)\n            return preSum[j];\n        return preSum[j] - preSum[i - 1];\n    }\n\n    long long get(int i, int j, int mid, const vector<int> &nums, const vector<long long> &preSum)\n    {\n        long long c1 = nums[mid] * 1LL * (mid - i + 1) - sum(i, mid, preSum);\n        long long c2 = sum(mid, j, preSum) - (nums[mid] * 1LL * (j - mid + 1));\n        return c1 + c2;\n    }\n\n    bool check(int mid, int n, long long k, const vector<int> &nums, const vector<long long> &preSum)\n    {\n        int i = 0, j = mid - 1;\n        long long ans = 1e18;\n        for (; j < n; j++, i++)\n        {\n            if ((j - i + 1) % 2 == 1)\n            {\n                long long c1 = get(i, j, (i + j) / 2, nums, preSum);\n                ans = min(ans, c1);\n            }\n            else\n            {\n                long long c1 = get(i, j, (i + j) / 2, nums, preSum);\n                long long c2 = get(i, j, (i + j) / 2 + 1, nums, preSum);\n                ans = min({ans, c1, c2});\n            }\n        }\n        return ans <= k;\n    }\n\n    int maxFrequencyScore(vector<int> &nums, long long k)\n    {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        vector<long long> preSum(n, nums[0]);\n        for (int i = 1; i < n; i++)\n        {\n            preSum[i] = preSum[i - 1] + nums[i];\n        }\n        int low = 1, high = n, ans = 1;\n        while (low <= high)\n        {\n            int mid = low + (high - low) / 2;\n            if (check(mid, n, k, nums, preSum))\n            {\n                ans = mid;\n                low = mid + 1;\n            }\n            else\n            {\n                high = mid - 1;\n            }\n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'Prefix Sum', 'C++']