Show problems as
Classic problem #3953HardArrayHash TableMathCombinatoricsEnumerationNumber Theory

Maximum Score with Co-Prime Element

Real-world version: Best Pick Plus What It Leaves Coprime
Tracked in this browser only
Read Maximum Score with Co-Prime Element on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Register values are given as nums, along with a ceiling maxVal.

Pick a whole number x from 1 to maxVal inclusive. Its score is x itself plus the total of every entry of nums sharing no common factor above one with x.

Return the largest score any pick can have.

Examples

Example 1

Input
nums = [14, 27, 6, 35, 11], maxVal = 30
Output
122

A pick shares a factor with some entries and not others, and the best pick trades its own size against what it rules out.

Example 2

Input
nums = [2, 4, 6, 8], maxVal = 1
Output
21

The ceiling leaves only a pick of one, which shares no factor above one with anything, so the score is one plus the whole register.

Example 3

Input
nums = [7, 7, 7, 7], maxVal = 7
Output
34

Every entry is 7, so a pick of 7 rules them all out and scores 7, while a pick of 6 keeps them all and scores 34.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= maxVal <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_score(nums: list[int], maxVal: int) -> int:
Java
public long maxScore(int[] nums, int maxVal)

More on the same topics