Maximize Pair Strength Using GCD solution and explanation
The problem
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] <= 105
Approach overview
Problem 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.
Solution
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).
class Solution:
def maxPairStrength(self, nums: list[int]) -> int:
n = len(nums)
ans = 0
for i in range(n):
for j in range(i + 1, n):
x = nums[i] * nums[j] // gcd(nums[i], nums[j]) ** 2
ans = max(ans, x)
return ansclass Solution {
public long maxPairStrength(int[] nums) {
int n = nums.length;
long ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
long g = gcd(nums[i], nums[j]);
long x = (long) nums[i] * nums[j] / (g * g);
ans = Math.max(ans, x);
}
}
return ans;
}
private long gcd(long a, long b) {
while (b != 0) {
long t = a % b;
a = b;
b = t;
}
return a;
}
}class Solution {
public:
long long maxPairStrength(vector<int>& nums) {
int n = nums.size();
long long ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
long long g = gcd(nums[i], nums[j]);
long long x = 1LL * nums[i] * nums[j] / (g * g);
ans = max(ans, x);
}
}
return ans;
}
};function maxPairStrength(nums: number[]): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const g = gcd(nums[i], nums[j]);
const x = Math.floor((nums[i] * nums[j]) / (g * g));
ans = Math.max(ans, x);
}
}
return ans;
}
function gcd(a: number, b: number): number {
while (b !== 0) {
const t = a % b;
a = b;
b = t;
}
return a;
}func maxPairStrength(nums []int) int64 {
n := len(nums)
var ans int64 = 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
g := gcd(int64(nums[i]), int64(nums[j]))
x := int64(nums[i]) * int64(nums[j]) / (g * g)
ans = max(ans, x)
}
}
return ans
}
func gcd(a, b int64) int64 {
for b != 0 {
a, b = b, a%b
}
return a
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumeration | O(n^2) | O(1) | Small arrays or simplicity |
Frequently asked questions
Is Maximize Pair Strength Using GCD easy or hard?
This problem is classified as Easy, with a 48.6% acceptance rate.
Maximize Pair Strength Using GCD Python/Java solution
Solutions are available on FleetCode in Python, Java, C++, Go, and TypeScript.
How to solve Maximize Pair Strength Using GCD in O(n^2)?
Use the enumeration approach by iterating through all pairs, computing their GCD, and calculating the strength.
What is the best approach for Maximize Pair Strength Using GCD?
The enumeration approach is the most straightforward, but it has O(n^2) time complexity. For small arrays, this is acceptable.
Is Maximize Pair Strength Using GCD asked at Google/Amazon/Meta?
This problem tests understanding of GCD and enumeration, which are common topics in coding interviews at major tech companies.
What data structure is used in Maximize Pair Strength Using GCD?
No specific data structure is required. The enumeration approach uses basic array traversal.
What is the time complexity of Maximize Pair Strength Using GCD?
The enumeration approach has a time complexity of O(n^2) due to checking all possible pairs.