# Maximize Score After N Operations Number Game Solution Amazon OA 2022

Page Contents

## Maximize Score After N Operations Number Game Solution

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

Program: Maximize Score After N Operations Number Game Solution in C++

``````class Solution {
int dp[8][1<<14];
int gcds[14][14];
int n;
public:
int recursion(vector<int> & nums, int ind, int mask){
if(ind-1 == n/2)
return 0;
int temp=0;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
}
}
}
}
int maxScore(vector<int>& nums) {
n = nums.size();
for(int i =0; i<n; i++)
for(int j =i+1; j<nums.size(); j++)
gcds[i][j] = __gcd(nums[i], nums[j]);
return recursion(nums, 1, 0);
}
};``````

Program: Maximize Score After N Operations Number Game Solution in Java

``````class Solution {
int[] map;
int[][] dp;
public int gcd(int a, int b){
if (b == 0)
return a;
return gcd(b, a % b);
}
public int maxScore(int[] nums) {
map = new int[16384];
Arrays.fill(map, -1);
dp = new int[nums.length][nums.length];
for(int i=0; i<dp.length; i++) {
for(int j=i+1; j<dp[0].length; j++) {
dp[i][j] = gcd(nums[i], nums[j]);
}
}
return find(nums, 0, 1);
}
public int find(int[] nums, int mask, int idx) {
int ans = 0;
for(int i=0; i<nums.length-1; i++) {
for(int j=i+1; j<nums.length; j++) {
int a = (1<<i) + (1<<j);
ans = Math.max(ans, idx*dp[i][j] + find(nums, mask|a, idx+1));
}
}
}
return ans;
}
}``````

Program: Maximize Score After N Operations Number Game Solution in Python

``````Python dp with memoization:
class Solution:
def maxScore(self, nums: List[int]) -> int:
def calc_score(nums, scores):
if not nums:
return 0
if tuple(nums) in scores:
return scores[tuple(nums)]
n = len(nums)/2
maxscore = 0
for i in range(int(2*n)):
for j in range(i+1,int(2*n)):
a = nums[i]
b=nums[j]
nums_copy = nums.copy()
#gcd = find_gcd(a,b)
nums_copy.remove(a)
nums_copy.remove(b)
score = int(n*math.gcd(a,b)+calc_score(nums_copy,scores))
if score>maxscore:
maxscore=score
scores[tuple(nums)]=maxscore
return maxscore
return calc_score(nums,{})
``````

Related: Amazon OA Online Assessment 2021 Questions and Answers