Maximize Score After N Operations/Number Game Solution Amazon OA 2021

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.

See Also : Amazon Online Assessment Questions 2021 Preparation

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,{})

Weekly Contest 247

• Maximum Product Difference Between Two Pairs
• Cyclically Rotating a Grid
• Number of Wonderful Substrings
• Count Ways to Build Rooms in an Ant Colony

Biweekly Contest 55

• Remove One Element to Make the Array Strictly Increasing
• Remove All Occurrences of a Substring
• Maximum Alternating Subsequence Sum
• Design Movie Rental System

June Long Challenge 2021 Solutions

• Maximum Frequent Subarray Sum solution codechef
• Dual Distance solution codechef
• Optimal Xor Set solution codechef
• Minimum Subtree Cover solution codechef
• Minimum Dual Area solution codechef
• Bitwise Tuples solution codechef
• Shortest Route solution codechef
• Bella ciao solution codechef
• Summer Heat solution codechef