0939HardArrayHash TableMathCombinatoricsEnumerationNumber Theory

Best Pick Plus What It Leaves Coprime

Tracked in this browser only

Trains the technique from

LeetCode 3953Maximum Score with Co-Prime Element

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_score(nums: list[int], maxVal: int) -> int:

Java

public long maxScore(int[] nums, int maxVal)

The intended approach

Time O(V log V + maxVal * 2^w) for values up to V and at most w distinct primes per pick, w being six at this ceiling.Space O(V) for the divisor totals and the smallest-prime-factor table.

Whether an entry shares a factor with `x` depends only on which primes divide `x`, so a pick's score is settled by `x` itself and by that prime set. Rather than testing every entry against every pick, work out first, for each possible divisor, the total of the entries it divides, which is one sweep over the multiples of each divisor. Then for a given `x`, the entries sharing a factor with it are those divisible by at least one of its primes, and their total comes from adding the totals for each prime, taking back the totals for each pair of primes, adding back the triples and so on, which is the usual crossing-out over the prime set. Subtracting that from the total of everything leaves the coprime total, and adding `x` gives the score. A value below the ceiling has at most six distinct primes, so each pick costs a bounded amount of work, and a table of smallest prime factors makes finding those primes immediate.

Pythonentry point: max_score

def max_score(nums, maxVal):
    top = maxVal
    for v in nums:
        if v > top:
            top = v
    spf = list(range(top + 1))
    p = 2
    while p * p <= top:
        if spf[p] == p:
            for q in range(p * p, top + 1, p):
                if spf[q] == q:
                    spf[q] = p
        p += 1
    holding = [0] * (top + 1)
    total = 0
    for v in nums:
        holding[v] += v
        total += v
    divides = [0] * (top + 1)
    for d in range(1, top + 1):
        run = 0
        for multiple in range(d, top + 1, d):
            run += holding[multiple]
        divides[d] = run
    best = 0
    for x in range(1, maxVal + 1):
        primes = []
        left = x
        while left > 1:
            q = spf[left]
            primes.append(q)
            while left % q == 0:
                left //= q
        shared = 0
        count = len(primes)
        for mask in range(1, 1 << count):
            product = 1
            bits = 0
            for i in range(count):
                if mask >> i & 1:
                    product *= primes[i]
                    bits += 1
            if bits % 2 == 1:
                shared += divides[product]
            else:
                shared -= divides[product]
        score = x + total - shared
        if score > best:
            best = score
    return best

The obvious version

Try every pick from one up to the ceiling and, for each, walk the whole register testing each entry against it with a greatest common divisor. Costs the register size per pick and works nothing out in advance.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_score(nums, maxVal):
    from math import gcd
    best = 0
    for x in range(1, maxVal + 1):
        score = x
        for v in nums:
            if gcd(v, x) == 1:
                score += v
        if score > best:
            best = score
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in