Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1799.html

1799. Maximize Score After N Operations

Level

Hard

Description

You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.

In the i-th 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] <= 10^6

Solution

In this problem, the 2 * n numbers in nums need to be divided into n groups, where each group contains 2 numbers. Find all possible combinations, and for each combination, calculate the score accordingly. Finally, return the maximum score.

  • class Solution {
        int maxScore = 0;
        Map<Long, Integer> map = new HashMap<Long, Integer>();
    
        public int maxScore(int[] nums) {
            int length = nums.length;
            int[] groups = new int[length];
            groups[0] = 1;
            for (int i = 1; i < length; i++) {
                groups[i] = 1;
                backtrack(nums, groups, 1, 2, nums.length / 2);
                groups[i] = 0;
            }
            return maxScore;
        }
    
        public void backtrack(int[] nums, int[] groups, int startIndex, int curr, int n) {
            int length = nums.length;
            if (curr > n) {
                int[][] groupsNums = new int[length][2];
                for (int i = 0; i < length; i++) {
                    groupsNums[i][0] = groups[i];
                    groupsNums[i][1] = nums[i];
                }
                Arrays.sort(groupsNums, new Comparator<int[]>() {
                    public int compare(int[] groupNum1, int[] groupNum2) {
                        return groupNum1[0] - groupNum2[0];
                    }
                });
                int[] gcds = new int[n];
                for (int i = 0; i < length; i += 2) {
                    int gcd = gcd(groupsNums[i][1], groupsNums[i + 1][1]);
                    gcds[i / 2] = gcd;
                }
                Arrays.sort(gcds);
                int score = 0;
                for (int i = 0; i < n; i++)
                    score += (i + 1) * gcds[i];
                maxScore = Math.max(maxScore, score);
                return;
            }
            for (int i = startIndex; i < length; i++) {
                if (groups[i] == 0) {
                    groups[i] = curr;
                    for (int j = i + 1; j < length; j++) {
                        if (groups[j] == 0) {
                            groups[j] = curr;
                            backtrack(nums, groups, i + 1, curr + 1, n);
                            groups[j] = 0;
                        }
                    }
                    groups[i] = 0;
                }
            }
        }
    
        public int gcd(int num1, int num2) {
            return num2 == 0 ? num1 : gcd(num2, num1 % num2);
        }
    }
    
    ############
    
    class Solution {
        public int maxScore(int[] nums) {
            int m = nums.length;
            int[][] g = new int[m][m];
            for (int i = 0; i < m; ++i) {
                for (int j = i + 1; j < m; ++j) {
                    g[i][j] = gcd(nums[i], nums[j]);
                }
            }
            int[] f = new int[1 << m];
            for (int k = 0; k < 1 << m; ++k) {
                int cnt = Integer.bitCount(k);
                if (cnt % 2 == 0) {
                    for (int i = 0; i < m; ++i) {
                        if (((k >> i) & 1) == 1) {
                            for (int j = i + 1; j < m; ++j) {
                                if (((k >> j) & 1) == 1) {
                                    f[k] = Math.max(
                                        f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);
                                }
                            }
                        }
                    }
                }
            }
            return f[(1 << m) - 1];
        }
    
        private int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }
    }
    
  • class Solution:
        def maxScore(self, nums: List[int]) -> int:
            m = len(nums)
            g = [[0] * m for _ in range(m)]
            for i in range(m):
                for j in range(i + 1, m):
                    g[i][j] = gcd(nums[i], nums[j])
            f = [0] * (1 << m)
            for k in range(1 << m):
                if (cnt := k.bit_count()) % 2 == 0:
                    for i in range(m):
                        if k >> i & 1:
                            for j in range(i + 1, m):
                                if k >> j & 1:
                                    f[k] = max(
                                        f[k],
                                        f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j],
                                    )
            return f[-1]
    
    
    
  • class Solution {
    public:
        int maxScore(vector<int>& nums) {
            int m = nums.size();
            int g[m][m];
            for (int i = 0; i < m; ++i) {
                for (int j = i + 1; j < m; ++j) {
                    g[i][j] = gcd(nums[i], nums[j]);
                }
            }
            int f[1 << m];
            memset(f, 0, sizeof f);
            for (int k = 0; k < 1 << m; ++k) {
                int cnt = __builtin_popcount(k);
                if (cnt % 2 == 0) {
                    for (int i = 0; i < m; ++i) {
                        if (k >> i & 1) {
                            for (int j = i + 1; j < m; ++j) {
                                if (k >> j & 1) {
                                    f[k] = max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt / 2 * g[i][j]);
                                }
                            }
                        }
                    }
                }
            }
            return f[(1 << m) - 1];
        }
    };
    
  • func maxScore(nums []int) int {
    	m := len(nums)
    	g := [14][14]int{}
    	for i := 0; i < m; i++ {
    		for j := i + 1; j < m; j++ {
    			g[i][j] = gcd(nums[i], nums[j])
    		}
    	}
    	f := make([]int, 1<<m)
    	for k := 0; k < 1<<m; k++ {
    		cnt := bits.OnesCount(uint(k))
    		if cnt%2 == 0 {
    			for i := 0; i < m; i++ {
    				if k>>i&1 == 1 {
    					for j := i + 1; j < m; j++ {
    						if k>>j&1 == 1 {
    							f[k] = max(f[k], f[k^(1<<i)^(1<<j)]+cnt/2*g[i][j])
    						}
    					}
    				}
    			}
    		}
    	}
    	return f[1<<m-1]
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    func gcd(a, b int) int {
    	if b == 0 {
    		return a
    	}
    	return gcd(b, a%b)
    }
    
  • function maxScore(nums: number[]): number {
        const m = nums.length;
        const f: number[] = new Array(1 << m).fill(0);
        const g: number[][] = new Array(m).fill(0).map(() => new Array(m).fill(0));
        for (let i = 0; i < m; ++i) {
            for (let j = i + 1; j < m; ++j) {
                g[i][j] = gcd(nums[i], nums[j]);
            }
        }
        for (let k = 0; k < 1 << m; ++k) {
            const cnt = bitCount(k);
            if (cnt % 2 === 0) {
                for (let i = 0; i < m; ++i) {
                    if ((k >> i) & 1) {
                        for (let j = i + 1; j < m; ++j) {
                            if ((k >> j) & 1) {
                                const t =
                                    f[k ^ (1 << i) ^ (1 << j)] +
                                    ~~(cnt / 2) * g[i][j];
                                f[k] = Math.max(f[k], t);
                            }
                        }
                    }
                }
            }
        }
        return f[(1 << m) - 1];
    }
    
    function gcd(a: number, b: number): number {
        return b ? gcd(b, a % b) : a;
    }
    
    function bitCount(i: number): number {
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }
    
    

All Problems

All Solutions