Hard

Maximize Score After N Operations

LAB

Pair all numbers over n operations. Operation i scores i times gcd(pair). Return the maximum total score.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2
  ]
}

Output
1

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Try all pairs of unused elements. Operation number derived from bit count.

Reveal reference solution +

pythonREFERENCE

def maxScore(self, nums: List[int]) -> int:
    m = len(nums)
    n = m // 2

    @cache
    def dp(mask):
        op = 1 + bin(mask).count('1') // 2
        if op > n:
            return 0

        ans = 0
        for i in range(m):
            if mask & (1 << i): continue
            for j in range(i + 1, m):
                if mask & (1 << j): continue
                new_mask = mask | (1 << i) | (1 << j)
                score = op * math.gcd(nums[i], nums[j]) + dp(new_mask)
                ans = max(ans, score)
        return ans

    return dp(0)

TimeO(n² × 2^n)

SpaceO(2^n)

Open on LeetCode ↗