Formatted question description: https://leetcode.ca/all/1838.html

# 1838. Frequency of the Most Frequent Element

## Level

Medium

## Description

The **frequency** of an element is the number of times it occurs in an array.

You are given an integer array `nums`

and an integer `k`

. In one operation, you can choose an index of `nums`

and increment the element at that index by `1`

.

Return *the maximum possible frequency of an element after performing at most *.

`k`

operations**Example 1:**

**Input:** nums = [1,2,4], k = 5

**Output:** 3

**Explanation:** Increment the first element three times and the second element two times to make nums = [4,4,4].

4 has a frequency of 3.

**Example 2:**

**Input:** nums = [1,4,8,13], k = 5

**Output:** 2

**Explanation:** 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.

**Example 3:**

**Input:** nums = [3,9,6], k = 2

**Output:** 1

**Constraints:**

`1 <= nums.length <= 10^5`

`1 <= nums[i] <= 10^5`

`1 <= k <= 10^5`

## Solution

Sort the array `nums`

. Calculate a new array `differences`

as the differences of adjacent elements in `nums`

, and calculate the prefix sums of `differences`

. Then use binary search to find the maximum frequency of the most frequent element.

```
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int length = nums.length;
long[] differences = new long[length];
for (int i = 1; i < length; i++)
differences[i] = (long) nums[i] - (long) nums[i - 1];
long[] prefixSums = new long[length];
for (int i = 1; i < length; i++)
prefixSums[i] = prefixSums[i - 1] + differences[i];
int low = 1, high = length;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (isPossible(nums, differences, prefixSums, mid, k))
low = mid;
else
high = mid - 1;
}
return low;
}
public boolean isPossible(int[] nums, long[] differences, long[] prefixSums, int freq, int k) {
int length = differences.length;
long times = 0;
for (int i = freq - 2; i >= 0; i--)
times += (long) nums[freq - 1] - (long) nums[i];
long minTimes = times;
for (int i = freq; i < length; i++) {
times = times - (prefixSums[i - 1] - prefixSums[i - freq]) + differences[i] * (freq - 1);
minTimes = Math.min(minTimes, times);
}
return minTimes <= (long) k;
}
}
```