LeetCode 3334: Find the Maximum Factor Score of Array
Problem Description
Explanation
To find the maximum factor score of the array after removing at most one element, we need to consider the LCM and GCD of the array elements with and without removing each element. We can achieve this by iterating through the array, calculating the GCD and LCM of the elements, and comparing the factor score when each element is removed. The maximum factor score will be the highest factor score obtained.
- Initialize variables to keep track of the maximum factor score.
- Iterate through the array and for each element:
- Calculate GCD and LCM of all elements excluding the current element.
- Update the maximum factor score if the product of GCD and LCM is greater than the current maximum.
- Return the maximum factor score.
Time complexity: O(n^2) where n is the number of elements in the array.
Space complexity: O(1)
Solutions
class Solution {
public int maxFactorScore(int[] nums) {
int maxScore = 0;
for (int i = 0; i < nums.length; i++) {
int currScore = 0;
int gcd = 0;
int lcm = 1;
for (int j = 0; j < nums.length; j++) {
if (j != i) {
gcd = calculateGCD(gcd, nums[j]);
lcm = calculateLCM(lcm, nums[j]);
}
}
currScore = gcd * lcm;
maxScore = Math.max(maxScore, currScore);
}
return maxScore;
}
private int calculateGCD(int a, int b) {
if (b == 0) {
return a;
}
return calculateGCD(b, a % b);
}
private int calculateLCM(int a, int b) {
return a * b / calculateGCD(a, b);
}
}Loading editor...