You are given an integer array nums.
Choose exactly one pair of distinct indices i and j. The strength of the pair is defined as (nums[i] * nums[j]) / gcd(nums[i], nums[j])2.
Return the maximum strength over all possible pairs.
Example 1:
Input: nums = [2,3,5]
Output: 15
Explanation:
Choosing i = 1 and j = 2 gives strength (3 * 5) / gcd(3, 5)2 = 15 / 1 = 15, which is the maximum over all pairs.
Example 2:
Input: nums = [4,6,8]
Output: 12
Explanation:
Choosing i = 1 and j = 2 gives strength (6 * 8) / gcd(6, 8)2 = 48 / 4 = 12, which is the maximum over all pairs.
Example 3:
Input: nums = [3,3]
Output: 1
Explanation:
Choosing i = 0 and j = 1 gives strength (3 * 3) / gcd(3, 3)2 = 9 / 9 = 1, the maximum over all pairs.
Constraints:
2 <= nums.length <= 20001 <= nums[i] <= 105Problem Overview: Given an array of integers, find the maximum pair strength where strength is defined as the sum of the pair multiplied by their GCD.
Approach 1: Enumeration (O(n^2))
Iterate through all possible pairs in the array, compute their GCD, and calculate the strength. Track the maximum strength encountered. This approach is straightforward but inefficient for large arrays. Use it when the array size is small or when simplicity is preferred over performance.
Recommended for interviews: Start with the enumeration approach to demonstrate understanding, but be prepared to discuss optimization strategies. Interviewers expect you to recognize the inefficiency and suggest improvements.
For more advanced topics, explore GCD and Enumeration on FleetCode.
We directly enumerate all pairs (i, j) where i < j, calculate the strength of each pair \frac{nums[i] times nums[j]}{\gcd(nums[i], nums[j])^2}, and take the maximum.
The greatest common divisor \gcd can be computed using the Euclidean algorithm.
The time complexity is O(n^2 times log M), where n is the length of the array nums and M is the maximum value in the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumeration | O(n^2) | O(1) | Small arrays or simplicity |
Maximize Pair Strength Using GCD | LeetCode 4010 | Weekly Contest 513 | Java Code | Developer Coder • Developer Coder • 121 views views
Watch 1 more video solutions →Practice Maximize Pair Strength Using GCD with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor