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 = 5modificationCost = 15 - 1 = 4Example 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 = 3modificationCost = 03 - 0 = 3Example 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 = 2modificationCost = 12 - 1 = 1
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= maxVal <= 105Problem 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| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pairwise GCD | O(n² log A) | O(1) | Small arrays or when constraints are tiny and simplicity matters |
| Prime Factorization + Inclusion-Exclusion | O(n log A) | O(A) | General case for large inputs where repeated GCD checks are too slow |
| Sieve + Divisor Frequency | O(A log A + n log A) | O(A) | When the maximum value is manageable and precomputation via sieve is feasible |
Practice Maximum Score with Co-Prime Element with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor