Skip to main content
Talentd

Maximum Score with Co-Prime Element - Solution & Explanation

HardArrayHash TableMathCombinatorics4 min readAsked at: ServiceNow, Atlassian
Practice this problem

Problem Statement

You are given an integer array nums of length n and an integer maxVal.

You may change any element in nums to any positive integer less than or equal to maxVal. Each such change costs 1.

Two integers are co-prime if their greatest common divisor (GCD) is 1.

After all modifications, you must choose an index i such that, nums[i] is co-prime with every other element nums[j].

Let:

  • selectedValue be the final value of nums[i] after modifications.
  • modificationCost be the total number of elements changed.

The score is defined as score = selectedValue - modificationCost.

Return the maximum possible score.

 

Example 1:

Input: nums = [3,4,6], maxVal = 5

Output: 4

Explanation:

Change nums[2] from 6 to 5, which costs 1. Choose nums[2] = 5, since it is co-prime with 3 and 4.

  • selectedValue = 5
  • modificationCost = 1
  • The score is 5 - 1 = 4

Example 2:

Input: nums = [1,2,3], maxVal = 4

Output: 3

Explanation:

No modifications are required. Choose nums[2] = 3, since it is co-prime with 1 and 2.

  • selectedValue = 3
  • modificationCost = 0
  • The score is 3 - 0 = 3

Example 3:

Input: nums = [2,2], maxVal = 1

Output: 1

Explanation:

Change nums[0] from 2 to 1, which costs 1. Choose nums[1] = 2, since it is co-prime with 1.

  • selectedValue = 2
  • modificationCost = 1
  • The score is ​​​​​​​2 - 1 = 1

 

Constraints:

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

Approach Overview

Problem Overview: You are given an array of integers and must compute the maximum score contributed by an element based on how many other elements are co-prime with it. Two numbers are co-prime when gcd(a, b) = 1. The task reduces to efficiently counting how many values in the array share no common prime factor with a candidate element and maximizing the resulting score.

Approach 1: Brute Force Pairwise GCD (O(n² log A) time, O(1) space)

The straightforward solution checks every pair of elements. For each element nums[i], iterate through all other elements and compute gcd(nums[i], nums[j]). If the GCD equals 1, the pair contributes to the score of nums[i]. Track the maximum score across all elements. This approach is easy to implement and clearly demonstrates the definition of co-prime pairs, but it becomes too slow when n grows large because every pair requires a GCD computation.

Approach 2: Prime Factorization + Inclusion-Exclusion (O(n log A) time, O(A) space)

The key observation: two numbers are not co-prime only if they share at least one prime factor. Instead of checking GCD against every element, factorize each number into its unique prime factors using a precomputed sieve. Maintain a frequency map for multiples of prime combinations. Using the inclusion–exclusion principle, count how many array elements share any prime factor with the current value. Subtract this from the total number of elements to obtain the number of co-prime partners. This transforms repeated GCD checks into arithmetic over factor subsets, which is significantly faster for large inputs.

Approach 3: Sieve + Frequency of Divisors (O(A log A + n log A) time, O(A) space)

Another scalable method builds a frequency table for values up to the maximum element and runs a modified sieve to count how many numbers are divisible by each integer. After computing the prime factorization for a candidate value, iterate through its factor subsets and use inclusion–exclusion with the divisor frequency table to determine how many elements share those factors. The number of co-prime elements is simply the total count minus those with shared factors. This approach is common in number theory problems and relies heavily on number theory, Sieve of Eratosthenes, and math optimizations.

Recommended for interviews: Start with the brute-force GCD scan to show understanding of the co-prime condition. Then move to the prime-factorization and inclusion–exclusion approach. Interviewers typically expect you to recognize that repeated gcd checks are wasteful and replace them with factor-based counting using a sieve. The optimized solution demonstrates comfort with number theory, precomputation, and combinatorial counting.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pairwise GCDO(n² log A)O(1)Small arrays or when constraints are tiny and simplicity matters
Prime Factorization + Inclusion-ExclusionO(n log A)O(A)General case for large inputs where repeated GCD checks are too slow
Sieve + Divisor FrequencyO(A log A + n log A)O(A)When the maximum value is manageable and precomputation via sieve is feasible

Video Solution

Leetcode 3953 | Maximum Score with Co-Prime Element | Leetcode biweekly contest 184 • CodeWithMeGuys • 596 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximum Score with Co-Prime Element easy or hard?
The problem is considered Hard because the naive GCD approach quickly becomes too slow. Efficient solutions require number theory concepts such as prime factorization, sieve preprocessing, and inclusion–exclusion counting.
Maximum Score with Co-Prime Element Python/Java solution
Python and Java solutions typically precompute smallest prime factors using a sieve, then factorize each number to generate prime subsets. Inclusion–exclusion determines how many elements share those factors. The final score for each element is computed using those counts and the maximum is returned.
How to solve Maximum Score with Co-Prime Element in O(n log A)?
Precompute smallest prime factors using a sieve. For each number, extract its unique prime factors and generate all subsets of those factors. Use inclusion–exclusion with a frequency table to count how many numbers share any of those factors. The remaining elements are co-prime with the current value, allowing you to compute the score efficiently.
What is the best approach for Maximum Score with Co-Prime Element?
The most efficient approach uses prime factorization with inclusion–exclusion. Instead of checking GCD against every element, factorize each number and count how many array values share those prime factors. Subtract that count from the total elements to determine how many are co-prime. This reduces the complexity to roughly O(n log A) with precomputation.
Is Maximum Score with Co-Prime Element asked at Google/Amazon/Meta?
Problems involving co-prime relationships, GCD properties, and sieve-based counting appear frequently in interviews at large tech companies. Variants using number theory, inclusion–exclusion, and prime factorization are common in Google and Amazon algorithm rounds.
What data structure is used in Maximum Score with Co-Prime Element?
Typical implementations rely on arrays or hash maps for frequency counting, along with a sieve array storing the smallest prime factor for each number. These structures enable fast factorization and efficient inclusion–exclusion counting.
What is the time complexity of Maximum Score with Co-Prime Element?
The brute-force approach runs in O(n² log A) because every pair requires a GCD computation. Optimized solutions using sieve-based factorization and inclusion–exclusion reduce the complexity to about O(n log A) after preprocessing primes up to the maximum value in the array.

Ready to solve this problem?

Practice Maximum Score with Co-Prime Element with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays