1799. Maximize Score After N Operations LeetCode Solution
In this guide, you will get 1799. Maximize Score After N Operations LeetCode Solution with the best time and space complexity. The solution to Maximize Score After N Operations 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 Maximize Score After N Operations
You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.
In the ith operation (1-indexed), you will:
Choose two elements, x and y.
Receive a score of i * gcd(x, y).
Remove x and y from nums.
Return the maximum score you can receive after performing n operations.
The function gcd(x, y) is the greatest common divisor of x and y.
Example 1:
Input: nums = [1,2]
Output: 1
Explanation: The optimal choice of operations is:
(1 * gcd(1, 2)) = 1
Example 2:
Input: nums = [3,4,6,8]
Output: 11
Explanation: The optimal choice of operations is:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
1799. Maximize Score After N Operations LeetCode Solution in C++
class Solution {
public:
int maxScore(vector<int>& nums) {
const int n = nums.size() / 2;
vector<vector<int>> mem(n + 1, vector<int>(1 << n * 2));
return maxScore(nums, 1, 0, mem);
}
private:
// Returns the maximum score you can receive after performing the k to n
// operations, where `mask` is the bitmask of the chosen numbers.
int maxScore(const vector<int>& nums, int k, int mask,
vector<vector<int>>& mem) {
if (k == mem.size())
return 0;
if (mem[k][mask] > 0)
return mem[k][mask];
for (int i = 0; i < nums.size(); ++i)
for (int j = i + 1; j < nums.size(); ++j) {
const int chosenMask = 1 << i | 1 << j;
if ((mask & chosenMask) == 0)
mem[k][mask] = max(mem[k][mask],
k * __gcd(nums[i], nums[j]) +
maxScore(nums, k + 1, mask | chosenMask, mem));
}
return mem[k][mask];
}
}; /* code provided by PROGIEZ */
1799. Maximize Score After N Operations LeetCode Solution in Java
class Solution {
public int maxScore(int[] nums) {
final int n = nums.length / 2;
int[][] mem = new int[n + 1][1 << (n * 2)];
return maxScore(nums, 1, 0, mem);
}
// Returns the maximum score you can receive after performing the k to n
// operations, where `mask` is the bitmask of the chosen numbers.
private int maxScore(int[] nums, int k, int mask, int[][] mem) {
if (k == mem.length)
return 0;
if (mem[k][mask] > 0)
return mem[k][mask];
for (int i = 0; i < nums.length; ++i)
for (int j = i + 1; j < nums.length; ++j) {
final int chosenMask = 1 << i | 1 << j;
if ((mask & chosenMask) == 0)
mem[k][mask] = Math.max(mem[k][mask], k * gcd(nums[i], nums[j]) +
maxScore(nums, k + 1, mask | chosenMask, mem));
}
return mem[k][mask];
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
} // code provided by PROGIEZ
1799. Maximize Score After N Operations LeetCode Solution in Python
class Solution:
def maxScore(self, nums: list[int]) -> int:
n = len(nums) // 2
@functools.lru_cache(None)
def dp(k: int, mask: int) -> int:
"""
Returns the maximum score you can receive after performing the k to n
operations, where `mask` is the bitmask of the chosen numbers.
"""
if k == n + 1:
return 0
res = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
chosenMask = 1 << i | 1 << j
if (mask & chosenMask) == 0:
res = max(
res, k * math.gcd(nums[i], nums[j]) + dp(k + 1, mask | chosenMask))
return res
return dp(1, 0) # code by PROGIEZ
