<p>The <strong>frequency</strong> of an element is the number of times it occurs in an array.</p>

<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. In one operation, you can choose an index of <code>nums</code> and increment the element at that index by <code>1</code>.</p>

<p>Return <em>the <strong>maximum possible frequency</strong> of an element after performing <strong>at most</strong> </em><code>k</code><em> operations</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,4], k = 5
<strong>Output:</strong> 3<strong>
Explanation:</strong> Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,4,8,13], k = 5
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,9,6], k = 2
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
</ul>

// Idea: Greedy, Prefix Sum, Binary Search, Sorting
class Solution {
public:
    // _BinarySearch
    int maxFrequency(vector<int>& nums, int k) {
        std::ranges::sort(nums);
        const auto& a = nums;
        const int n = a.size();
        // create the prefix sum array, for quick range-sum
        vector<long long> ps(n);
        // Bug: partial_sum()'s accumulator is int32, so it cannot handle int64.
        // partial_sum(a.begin(), a.end(), ps.begin(),
        //             [](long long accum, int e) { return accum + e; });
        // cout << "n: " << n << ", first: " << a.front() << ", last: " <<
        // a.back()
        //      << ", total: " << ps.back() << endl;
        // for (int i = 0; i < n - 1; ++i) {
        //     if (ps[i] >= ps[i + 1]) {
        //         cout << "wrong: " << ps[i] << " vs " << ps[i + 1] << endl;
        //     }
        // }
        for (long long i = 0, sum = 0; i < n; ++i) {
            sum += a[i];
            ps[i] = sum;
        }
        int res = 1;
        for (int i = n - 1; i >= 1; --i) {
            // check if the whole range [0, i] is possible
            // {
            //     long long existing = ps[i];
            //     long long required = (long long)a[i] * (i + 1);
            //     if (existing + k >= required) {
            //         cout << "can make [0, " << i << "]" << endl;
            //         return i + 1;
            //     } else {
            //         cout << "lacked " << required - existing + k
            //              << " to make [0, " << i << "]" << endl;
            //     }
            // }
            // binary search in [0, i]
            int low = 0;
            int high = i;
            int best = i;
            while (low <= high) {
                int mid = (low + high) / 2;
                long long existing = ps[i] - (mid > 0 ? ps[mid - 1] : 0);
                long long required = (long long)a[i] * (i - mid + 1);
                if (existing + k >= required) { // can make it
                    // cout << "low: " << low << ", high: " << high
                    //      << ", mid: " << mid << ", existing: " <<
                    //      existing
                    //      << ", required: " << required << ", Good" <<
                    //      endl;
                    best = min(best, mid);
                    high = mid - 1;
                } else {
                    // cout << "i: " << i << ", low: " << low << ", high: " <<
                    // high
                    //      << ", mid: " << mid << ", existing: " << existing
                    //      << ", required: " << required
                    //      << ", failed: diff: " << required - existing - k
                    //      << endl;
                    low = mid + 1;
                }
            }
            // [best ... i] can be made the same as a[i]
            res = max(res, i - best + 1);
        }
        return res;
    }
    // sliding window
    int maxFrequency_SlidingWindow(vector<int>& A, long k) {
        int i = 0, j = 0;
        sort(A.begin(), A.end());
        for (j = 0; j < A.size(); ++j) {
            k += A[j];
            if (k < (long)A[j] * (j - i + 1))
                k -= A[i++];
        }
        return j - i;
    }
};
113600