HardArrayHash TableMathCombinatoricsEnumerationNumber TheoryUpdated Sep 2026

3953. Maximum Score with Co-Prime Element

Asked at Atlassian

Difficulty

Hard

Time

O(maxVal log log maxVal + n * lo

Space

O(maxVal)

Pattern

Array

Companies

1

Problem

You are given an integer array nums and an integer maxVal. You may replace any element of nums with any positive integer that is at most maxVal. Each element you replace costs 1 point.

After all replacements, you must pick one index i. The final value at nums[i] must be co-prime with every other final element in the array. Two numbers are co-prime when their greatest common divisor (GCD) is 1 — they share no common prime factor.

Let selectedValue be the final value at index i, and modificationCost be how many elements you changed in total (including nums[i] itself if you changed it). The score is selectedValue - modificationCost. Return the maximum possible score.

Note that the co-prime rule applies to the whole final array, not just to the chosen index. So every other element must also be changed if it shares a factor with your chosen value.

Pick one value, fix everything else

nums346012Start: nums = [3,4,6], maxVal = 5after345012Change 6 → 5 (cost 1). Now 5 shares no factor with 3or 4.selectedValue = 5modificationCost = 1score = 5 − 1 = 4
The chosen value must be co-prime with every other final element, so any element sharing a prime factor with it must be changed.

Constraints

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

Examples

Example 1
Inputnums = [3,4,6], maxVal = 5
Output4
WhyChange the 6 into 5 (cost 1). Now the array is [3,4,5]. Pick index 2 with value 5: gcd(5,3)=1 and gcd(5,4)=1, so it is co-prime with both others. Score = 5 - 1 = 4.
Example 2
Inputnums = [1,2,3], maxVal = 4
Output3
WhyNo changes are needed. Pick index 2 with value 3: gcd(3,1)=1 and gcd(3,2)=1. Score = 3 - 0 = 3.
Example 3
Inputnums = [2,2], maxVal = 1
Output1
WhyChange nums[0] from 2 to 1 (cost 1). The array becomes [1,2]. Pick index 1 with value 2: gcd(2,1)=1, so it is co-prime with the other element. Score = 2 - 1 = 1.

Asked At

1 companies
CompanyDifficulty
AtlassianHardView all Atlassian questions →

How to Think About It

1

Brute force: enumerate all 2^n subsets and check if each subset is pairwise co-prime — O(2^n * n²).

2

Precompute prime factors for each number using a sieve up to the maximum element value.

3

Use bitmask DP where each bit represents whether a prime factor has been used.

4

For each element, try adding it only if none of its prime factors are already in the bitmask.

5

The optimal approach uses inclusion-exclusion or bitmask DP with O(n * 2^p) where p is the number of distinct primes.

Optimal Approach

Precompute prime factorizations for all array elements using a sieve. Identify all distinct prime factors across the array. Assign each prime a bit position in a bitmask. Use DP where dp[mask] represents the maximum sum achievable using exactly the primes in mask. For each element, compute its prime bitmask and update dp by transitioning from all valid previous masks (those sharing no common bits). The answer is the maximum value across all dp entries. This runs in O(n * 2^p) where p is the count of distinct primes.

Try each candidate value

sieve smallest prime factorfactor every nums[j]for v = 1..maxVal: count bad jscore = v − badThe whole algorithm in four steps.nums346012Candidate v = 5: 3 and 4 are fine (green), 6 sharesfactor 2? No — 6 shares nothing with 5, but 6 itselfis the one we change. Here bad = 1.bad(v) = #{ j : gcd(nums[j], v) > 1 }score(v) = v − bad(v)answer = max over v in [1, maxVal]
For a candidate v, count how many elements are already co-prime with v; the rest must be changed.
ComplexityTime O(maxVal log log maxVal + n * loSpace O(maxVal)The sieve costs O(maxVal log log maxVal); factorising every element costs O(n log maxVal), and the per-candidate check is a small constant because a candidate only needs its distinct prime factors.

What Trips People Up in Real Interviews

1

Clarify whether all pairs must be co-pair or just adjacent elements in the chosen order.

2

Ask about the range of array values — this determines the number of distinct primes for the bitmask.

3

Mention the sieve precomputation for prime factorization as an important optimization.

4

Discuss that bitmask DP works when the number of distinct primes is small (≤ 20).

5

For larger values, consider a different approach like maximum-weight independent set on a co-prime graph.

Solution Code

O(maxVal log log maxVal + n * lo time
def max_co_prime_score(arr):
    max_val = max(arr) if arr else 0
    spf = list(range(max_val + 1))
    for i in range(2, int(max_val**0.5) + 1):
        if spf[i] == i:
            for j in range(i*i, max_val + 1, i):
                if spf[j] == j:
                    spf[j] = i
    primes = []
    prime_to_bit = {}
    for num in arr:
        temp = num
        while temp > 1:
            p = spf[temp]
            if p not in prime_to_bit:
                prime_to_bit[p] = len(primes)
                primes.append(p)
            while temp % p == 0:
                temp //= p
    n = len(primes)
    dp = [0] * (1 << n)
    for num in arr:
        temp = num
        mask = 0
        while temp > 1:
            p = spf[temp]
            mask |= (1 << prime_to_bit[p])
            while temp % p == 0:
                temp //= p
        for state in range((1 << n) - 1, -1, -1):
            if (state & mask) == 0:
                new_state = state | mask
                dp[new_state] = max(dp[new_state], dp[state] + num)
    return max(dp)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Maximum Score with Co-Prime Element problem?

Given an array of integers, find the maximum sum of a subset where no two selected elements share a common divisor greater than 1 (i.e., all pairs in the subset must be co-prime). This problem combines number theory with dynamic programming. You need to enumerate valid subsets while tracking which prime factors have been used.

How do you solve Maximum Score with Co-Prime Element?

The optimal approach runs in O(maxVal log log maxVal + n * lo time and O(maxVal) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Maximum Score with Co-Prime Element?

Maximum Score with Co-Prime Element is asked at Atlassian. It is a hard difficulty problem.

What are common mistakes on Maximum Score with Co-Prime Element?
  • Clarify whether all pairs must be co-pair or just adjacent elements in the chosen order.
  • Ask about the range of array values — this determines the number of distinct primes for the bitmask.
  • Mention the sieve precomputation for prime factorization as an important optimization.
  • Discuss that bitmask DP works when the number of distinct primes is small (≤ 20).
  • For larger values, consider a different approach like maximum-weight independent set on a co-prime graph.