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
andy
. - Receive a score of
i * gcd(x, y)
. - Remove
x
andy
fromnums
.
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
.
Also See: Amazon OA Online Assessment 2021 Questions and Answers
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 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 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 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,{})
Also See: AMCAT Study Materials, Preparation Guide
Also See: Microsoft Online Assessment Questions and Solution
Amazon Online Assessment Questions:
- Robot Bounded in Box
- Number Game
- Find All Combination of Numbers Sum to Target / Shopping Options
- Fill the Truck
- Music Pairs
- Slowest key
- Five Star Seller
- Split String Into Unique Primes
- Storage Optimization
- Minimum Difficulty of a Job Schedule
- Autoscale Policy, Utilization Check
- Optimal Utilization
- Merge Two Sorted Lists
- Two Sum Unique Pairs
- Shopping Patterns
- Reorder Data in Log Files
- Top K Frequent Words
- Trees Height
- Counting Binary Substrings Amazon OA Solution
- Grid Connections Amazon OA Solution
- Shipment Imbalance Amazon OA Solution
- Max Profit Amazon OA Solution
- Find Lowest Price Amazon OA Solution
- Simple Cipher Amazon OA Solution
- Decode String Frequency Amazon OA Solution
- Valid Discount Coupons Amazon OA Solution
- Count Maximum Teams Amazon OA Solution
- Minimum Coin Flips Amazon OA Solution