Fewest Replacements for a Consecutive Set
Company: Juspay
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
One operation replaces any entry of `nums` with any integer. Return the fewest replacements needed to make all `n` entries distinct with maximum minus minimum equal to `n-1`. The final array need not be sorted; its values must be exactly one interval of consecutive integers.
```cpp
class Solution {
public:
int minOperations(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
nums = [5,5,6,9]
Output: 2
Explanation: Keep 5 and 6 and replace the others by 7 and 8.
```
**Example 2:**
```text
nums = [8,6,7]
Output: 0
Explanation: The distinct values already fill the interval [6,8].
```
### Constraints
- `1 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^9`.
### Clarifying Questions
Replacements may use any integer. The final array must contain distinct values as required by the continuity condition.
```hint Inspect the structure
How many distinct original values can fit inside an interval containing n consecutive integers?
```
### Reasoning checkpoints
- Minimize replacements while meeting both distinctness and the required value span.
- Account for duplicate input entries without changing the original array length used by the goal.
### Optional extensions
How would the objective change if the final order also had to be sorted?
Overview: Fewest Replacements for a Consecutive Set. Replace any array entry by any integer in one operation. Return the smallest number of replacements needed so that all n entries are distinct and maximum minus minimum equals n-1. Array order is unrestricted; the final values form one consecutive integer interval.