Maximum Score with Co-Prime Element
Asked at Atlassian
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | HARD | View all Atlassian questions → |
How to Think About It
Brute force: enumerate all 2^n subsets and check if each subset is pairwise co-prime — O(2^n * n²).
Precompute prime factors for each number using a sieve up to the maximum element value.
Use bitmask DP where each bit represents whether a prime factor has been used.
For each element, try adding it only if none of its prime factors are already in the bitmask.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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)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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.