Remove Elements to Balance the Remaining Values
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Remove Elements to Balance the Remaining Values
You are given an integer array `nums` and an integer `k`.
A nonempty array is **balanced** when its maximum value is at most `k` times its minimum value. You may remove any elements from `nums`, but at least one element must remain.
Return the minimum number of elements to remove so that the remaining values are balanced. A single remaining element is always balanced under the stated bounds.
### C++ Interface
```cpp
class Solution {
public:
int minRemoval(vector<int>& nums, int k) {
}
};
```
### Examples
**Example 1**
**Input:** `nums = [12, 3, 7, 6, 25], k = 2`
**Output:** `2`
**Explanation:** Remove `3` and `25`. The remaining values `[12, 7, 6]` satisfy `12 <= 2 * 6`. Keeping four values is impossible: if `25` is kept with any other available value, the condition fails; excluding only `25` leaves minimum `3` and maximum `12`, which also fails.
**Example 2**
**Input:** `nums = [8, 8, 2, 8], k = 1`
**Output:** `1`
**Explanation:** Remove `2` and keep the three copies of `8`. With `k = 1`, all remaining values must be equal. The full input is not balanced, so zero removals cannot work.
### Constraints
- `1 <= nums.length <= 100000`
- `1 <= nums[i] <= 1000000000`
- `1 <= k <= 100000`
### Clarifying Questions
- Must the removed elements occupy adjacent positions? No; any elements may be removed.
- Can all elements be removed? No. At least one must remain.
- Are equal values separate elements? Yes; each occurrence counts toward the number kept or removed.
- Must the function erase elements from `nums`? No; the requested output is only the removal count.
### What a Strong Answer Covers
- A minimum removal count with a nonempty balanced remainder.
- Correct behavior for equal values, `k = 1`, and an already balanced input.
- Safe arithmetic and a complexity analysis for the full value and length bounds.
### Follow-up Questions
- What tie policy would be useful if the API also returned the indices to remove?
- If at least two elements had to remain, how should the API represent an impossible instance?
```hint Work with value extremes
After sorting a copy, consider the longest consecutive block whose largest value is at most `k` times its smallest. Check the product using a 64-bit integer.
```
Overview: Find the fewest removals needed so a nonempty array has maximum value at most k times its minimum, including duplicates and large integer values.