Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 14

Description

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

Example 3:

Input: nums = [1,2,3,4,5,6]
Output: 14
Explanation: The optimal choice of operations is:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

Constraints:

• 1 <= n <= 7
• nums.length == 2 * n
• 1 <= nums[i] <= 106

Solution

class Solution {
  int len;
  int n;
  int solve(
    vector<int>& dp,
    vector<vector<int>>& gcd,
    int mask,
    int ops
  ) {
    if(ops > n) return 0;
    if(dp[mask]) return dp[mask];

    int result = 0;
    for(int i = 0; i < len; ++i) {
      if(mask & (1 << i)) continue;
      for(int j = 0; j < len; ++j) {
        if(i == j) continue;
        if(mask & (1 << j)) continue;
        int newMask = mask | (1 << i) | (1 << j);
        result = max(result, ops * gcd[i][j] + solve(dp, gcd, newMask, ops + 1));
      }
    }

    return dp[mask] = result;
  }
public:
  int maxScore(vector<int>& nums) {
    len = nums.size();
    n = len / 2;
    vector<int> dp(1 << len);
    vector<vector<int>> gcd(len, vector<int>(len));

    for(int i = 0; i < len; ++i) {
      for(int j = i + 1; j < len; ++j) {
        gcd[i][j] = gcd[j][i] = __gcd(nums[i], nums[j]);
      }
    }
    return solve(dp, gcd, 0, 1);
  }
};

// Accepted
// 76/76 cases passed (156 ms)
// Your runtime beats 72.32 % of cpp submissions
// Your memory usage beats 49.83 % of cpp submissions (9 MB)