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;
if(dp[ind][mask]!=0)
return dp[ind][mask];
int temp=0;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
int tempMask = (1<<i)+(1<<j);
if((tempMask & mask) ==0){
temp = max(temp, ind * gcds[i][j] + recursion(nums, ind+1, mask|tempMask));
}
}
}
return dp[ind][mask] = temp;
}
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) {
if(map[mask] != -1) return map[mask];
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);
if((mask&a) == 0) {
ans = Math.max(ans, idx*dp[i][j] + find(nums, mask|a, idx+1));
}
}
}
map[mask] = ans;
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,{})
Amazon OA 2023 Questions with Solution
- Shopping Patterns Solution Amazon OA 2023
- Reorder Data in Log Files Solution Amazon OA 2023
- Top K Frequent Words Solution Amazon OA 2023
- Trees Height Solution Amazon OA SDE 2023
- Counting Binary Substrings Amazon OA 2023
- Grid Connections Amazon OA 2023
- Shipment Imbalance Amazon OA 2023
- Max Profit Amazon OA 2023
- Find Lowest Price Amazon OA 2023
- Decode String Frequency Amazon OA 2023
- Simple Cipher Amazon OA 2023
- Valid Discount Coupons Amazon OA 2023 Solution
- Count Maximum Teams Amazon OA 2023
- Minimum Coin Flips Amazon OA 2023
- Max Average Stock Price Amazon OA 2023 Solution
- Robot Bounded In Circle Amazon OA 2023
- Shopping Options Amazon OA 2023 Solution
- Fill The Truck Maximum Units on a Truck Amazon OA Solution
- Slowest Key Amazon OA 2023 Solution
- Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
- Split String Into Unique Primes Amazon OA 2023 Solution
- Storage Optimization Amazon OA 2023 Solution
- Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
- Autoscale Policy Utilization Check Amazon OA 2023
- Optimal Utilization Solution Amazon OA 2023
- Merge Two Sorted Lists Solution Amazon OA 2023
- Two Sum Unique Pairs Solution Amazon OA 2023
- Amazon Music Pairs Amazon OA 2023 Solution
- Class Grouping Amazon OA 2023 Solution
- Find Max products Amazon OA 2023 Solution
- Get encrypted number Amazon OA 2023 Solution
- Find Total Imbalance Amazon OA 2023 Solution
- Find Total Power Amazon OA 2023 Solution