Maximum Score with One Universally Coprime Element

# Maximum Score with One Universally Coprime Element You are given a positive integer array `nums` and a positive integer `maxVal`. You may replace any elements with positive integers at most `maxVal`. The cost is the number of elements whose values you change. After all changes, choose one index `i` whose value is coprime with every other final array element: for every `j != i`, their greatest common divisor must be `1`. Your score is: `final value at index i - number of changed elements`. Return the maximum possible score. ### Function `int maxScore(vector<int>& nums, int maxVal)` ### Example 1 **Input:** `nums = [12, 12, 5], maxVal = 4` **Output:** `11` **Explanation:** Keep the first `12` and replace the second with `1`, leaving `[12, 1, 5]`. Choose the unchanged `12`, which is coprime with `1` and `5`. The score is `12 - 1 = 11`. No unchanged `12` can be chosen without fixing the other `12`. ### Example 2 **Input:** `nums = [6, 6], maxVal = 8` **Output:** `6` **Explanation:** Replace one `6` with `7`, then choose the `7`. It is coprime with the remaining `6`, so the score is `7 - 1 = 6`. Another optimum is `[8, 1]`, which changes both elements and scores `8 - 2 = 6`. ### Constraints - `1 <= nums.length <= 100000` - `1 <= nums[i] <= 100000` - `1 <= maxVal <= 100000` ### Clarifications - `maxVal` restricts replacement values. An original element greater than `maxVal` may remain unchanged and may be selected. - Only the chosen element must be coprime with every other element. The other elements need not be pairwise coprime. - The selected element itself may be changed, and such a change counts toward the cost. - You may make no changes if the chosen element already satisfies the condition. - With one array element, the condition involving other indices is automatically satisfied. ### What a Strong Answer Covers - Accounting for both changes to the chosen element and changes to conflicting other elements. - Distinguishing existing values from values that must be created within the replacement limit. - Handling repeated values, value `1`, and the full numeric and array-size limits.