3334. Find the Maximum Factor Score of Array LeetCode Solution
In this guide, you will get 3334. Find the Maximum Factor Score of Array LeetCode Solution with the best time and space complexity. The solution to Find the Maximum Factor Score of Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Maximum Factor Score of Array
You are given an integer array nums.
The factor score of an array is defined as the product of the LCM and GCD of all elements of that array.
Return the maximum factor score of nums after removing at most one element from it.
Note that both the LCM and GCD of a single number are the number itself, and the factor score of an empty array is 0.
Example 1:
Input: nums = [2,4,8,16]
Output: 64
Explanation:
On removing 2, the GCD of the rest of the elements is 4 while the LCM is 16, which gives a maximum factor score of 4 * 16 = 64.
Example 2:
Input: nums = [1,2,3,4,5]
Output: 60
Explanation:
The maximum factor score of 60 can be obtained without removing any elements.
3334. Find the Maximum Factor Score of Array LeetCode Solution in C++
class Solution {
public:
long long maxScore(vector<int>& nums) {
const int n = nums.size();
// prefixGcd[i] := GCD of nums[0..i]
// prefixLcm[i] := LCM of nums[0..i]
const auto [prefixGcd, prefixLcm] = getPrefix(nums);
// suffixGcd[i] := GCD of nums[i..n - 1]
// suffixLcm[i] := LCM of nums[i..n - 1]
const auto [suffixGcd, suffixLcm] = getSuffix(nums);
long ans = suffixGcd[0] * suffixLcm[0];
for (int i = 0; i < n; ++i) {
const long gcd1 = i > 0 ? prefixGcd[i - 1] : 0;
const long gcd2 = i + 1 < n ? suffixGcd[i + 1] : 0;
const long lcm1 = i > 0 ? prefixLcm[i - 1] : 1;
const long lcm2 = i + 1 < n ? suffixLcm[i + 1] : 1;
const long score = gcd(gcd1, gcd2) * lcm(lcm1, lcm2);
ans = max(ans, score);
}
return ans;
}
private:
// Returns the prefix GCD and LCM arrays.
pair<vector<long>, vector<long>> getPrefix(const vector<int>& nums) {
vector<long> prefixGcd;
vector<long> prefixLcm;
long currGcd = 0;
long currLcm = 1;
for (const int num : nums) {
currGcd = gcd(currGcd, num);
currLcm = lcm(currLcm, num);
prefixGcd.push_back(currGcd);
prefixLcm.push_back(currLcm);
}
return {prefixGcd, prefixLcm};
}
// Returns the suffix GCD and LCM arrays.
pair<vector<long>, vector<long>> getSuffix(const vector<int>& nums) {
vector<long> suffixGcd;
vector<long> suffixLcm;
long currGcd = 0;
long currLcm = 1;
for (int i = nums.size() - 1; i >= 0; --i) {
currGcd = gcd(currGcd, nums[i]);
currLcm = lcm(currLcm, nums[i]);
suffixGcd.push_back(currGcd);
suffixLcm.push_back(currLcm);
}
ranges::reverse(suffixGcd);
ranges::reverse(suffixLcm);
return {suffixGcd, suffixLcm};
}
}; /* code provided by PROGIEZ */
3334. Find the Maximum Factor Score of Array LeetCode Solution in Java
class Solution {
public long maxScore(int[] nums) {
final int n = nums.length;
// prefixGcd[i] := GCD of nums[0..i]
// prefixLcm[i] := LCM of nums[0..i]
long[][] prefix = getPrefix(nums);
long[] prefixGcd = prefix[0];
long[] prefixLcm = prefix[1];
// suffixGcd[i] := GCD of nums[i..n - 1]
// suffixLcm[i] := LCM of nums[i..n - 1]
long[][] suffix = getSuffix(nums);
long[] suffixGcd = suffix[0];
long[] suffixLcm = suffix[1];
long ans = suffixGcd[0] * suffixLcm[0];
for (int i = 0; i < n; ++i) {
final long gcd1 = i > 0 ? prefixGcd[i - 1] : 0;
final long gcd2 = i + 1 < n ? suffixGcd[i + 1] : 0;
final long lcm1 = i > 0 ? prefixLcm[i - 1] : 1;
final long lcm2 = i + 1 < n ? suffixLcm[i + 1] : 1;
final long score = gcd(gcd1, gcd2) * lcm(lcm1, lcm2);
ans = Math.max(ans, score);
}
return ans;
}
// Returns the prefix GCD and LCM arrays.
private long[][] getPrefix(int[] nums) {
long[] prefixGcd = new long[nums.length];
long[] prefixLcm = new long[nums.length];
long currGcd = 0;
long currLcm = 1;
for (int i = 0; i < nums.length; ++i) {
currGcd = gcd(currGcd, nums[i]);
currLcm = lcm(currLcm, nums[i]);
prefixGcd[i] = currGcd;
prefixLcm[i] = currLcm;
}
return new long[][] {prefixGcd, prefixLcm};
}
// Returns the suffix GCD and LCM arrays.
private long[][] getSuffix(int[] nums) {
long[] suffixGcd = new long[nums.length];
long[] suffixLcm = new long[nums.length];
long currGcd = 0;
long currLcm = 1;
for (int i = nums.length - 1; i >= 0; --i) {
currGcd = gcd(currGcd, nums[i]);
currLcm = lcm(currLcm, nums[i]);
suffixGcd[i] = currGcd;
suffixLcm[i] = currLcm;
}
return new long[][] {suffixGcd, suffixLcm};
}
private long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
private long lcm(long a, long b) {
return a * (b / gcd(a, b));
}
} // code provided by PROGIEZ
3334. Find the Maximum Factor Score of Array LeetCode Solution in Python
class Solution:
def maxScore(self, nums: list[int]) -> int:
n = len(nums)
# prefixGcd[i] := GCD of nums[0..i]
# prefixLcm[i] := LCM of nums[0..i]
prefixGcd, prefixLcm = self._getPrefix(nums)
# suffixGcd[i] := GCD of nums[i..n - 1]
# suffixLcm[i] := LCM of nums[i..n - 1]
suffixGcd, suffixLcm = self._getSuffix(nums)
ans = suffixGcd[0] * suffixLcm[0]
for i in range(n):
gcd1 = prefixGcd[i - 1] if i > 0 else 0
gcd2 = suffixGcd[i + 1] if i + 1 < n else 0
lcm1 = prefixLcm[i - 1] if i > 0 else 1
lcm2 = suffixLcm[i + 1] if i + 1 < n else 1
score = math.gcd(gcd1, gcd2) * math.lcm(lcm1, lcm2)
ans = max(ans, score)
return ans
def _getPrefix(self, nums: list[int]) -> tuple[list[int], list[int]]:
"""Returns the prefix GCD and LCM arrays."""
prefixGcd = []
prefixLcm = []
currGcd = 0
currLcm = 1
for num in nums:
currGcd = math.gcd(currGcd, num)
currLcm = math.lcm(currLcm, num)
prefixGcd.append(currGcd)
prefixLcm.append(currLcm)
return prefixGcd, prefixLcm
def _getSuffix(self, nums: list[int]) -> tuple[list[int], list[int]]:
"""Returns the suffix GCD and LCM arrays."""
suffixGcd = []
suffixLcm = []
currGcd = 0
currLcm = 1
for num in reversed(nums):
currGcd = math.gcd(currGcd, num)
currLcm = math.lcm(currLcm, num)
suffixGcd.append(currGcd)
suffixLcm.append(currLcm)
return list(reversed(suffixGcd)), list(reversed(suffixLcm)) # code by PROGIEZ
