Problem 1799

Abstract / Summary

Given a list of numbers and operations, choose numbers to maximize a score by following allowed steps.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1799.py

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        size = len(nums)

        # bitmask
        all = (1 << size) - 1

        # precompute GCDs
        g = []
        for a in range(size):
            g.append([])
            for b in range(size):
                g[-1].append(gcd(nums[a], nums[b]))

        @cache
        def deeper(picked):
            if picked == all:
                return 0

            best   = 0
            factor = (picked.bit_count() // 2) + 1

            for a in range(size):
                maska = 1 << a
                if picked & maska:
                    continue

                for b in range(a + 1, size):
                    maskb = 1 << b
                    if picked & maskb:
                        continue

                    current = factor * g[a][b]
                    next = picked | maska | maskb
                    best = max(best, current + deeper(next))

            return best

        return deeper(0)
39 lines | 1027 bytes | submitted November 4, 2023 | GitHub   7% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 58% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Backtracking
  • Bit Manipulation
  • Bitmask
  • Dynamic Programming
  • Math
  • Number Theory
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves a combinatorial optimization problem on an integer array. It selects pairs of indices, computes a score based on the greatest common divisor (GCD) of the paired values, multiplies the GCD by an operation-dependent factor, and seeks the maximum total score achievable by pairing all elements exactly once. The algorithm relies on exhaustive search with memoization, bitmask representation of the selection state, and precomputed GCD values to keep the exploration tractable for the given constraints.

Bitmask Representation

The algorithm encodes the set of already-picked indices as a binary mask. Each bit corresponds to a position in the input list; a set bit indicates that the element at that position has been paired. The mask for the full selection is built as

size = len(nums)
all = (1 << size) - 1

When size is zero, all evaluates to zero, and the recursion terminates immediately, correctly handling an empty input array.

Precomputation of GCD Values

To avoid repeated GCD calculations during the recursive search, the code constructs a two-dimensional list g where g[a][b] stores gcd(nums[a], nums[b]). The nested loops fill the matrix:

g = []
for a in range(size):
    g.append([])
    for b in range(size):
        g[-1].append(gcd(nums[a], nums[b]))

This step ensures that each pair’s GCD is computed exactly once, turning a potentially expensive operation into a constant-time lookup later in the algorithm.

Memoized Depth-First Search

The core of the solution is a depth-first search function deeper that receives the current mask picked. The function is decorated with @cache, which automatically stores results for each distinct mask, preventing redundant recomputation of identical subproblems.

@cache
def deeper(picked):
    if picked == all:
        return 0

    best   = 0
    factor = (picked.bit_count() // 2) + 1

    # pair selection loops omitted for brevity
    return best

When the mask equals all, every element has been paired, and the recursion returns a base score of zero. The use of picked.bit_count() (available in Python 3.8+) efficiently counts the number of set bits, allowing the factor to be derived directly from the number of already formed pairs.

Pair Selection and Score Accumulation

Inside deeper, the algorithm iterates over all unordered pairs of indices that have not yet been selected. For each candidate pair (a, b), it constructs masks for the individual indices, checks their availability, computes the current contribution, and recurses with the updated mask.

for a in range(size):
    maska = 1 << a
    if picked & maska:
        continue

    for b in range(a + 1, size):
        maskb = 1 << b
        if picked & maskb:
            continue

        current = factor * g[a][b]
        next = picked | maska | maskb
        best = max(best, current + deeper(next))

The continue statements skip indices already present in picked. The expression picked | maska | maskb produces the new mask after adding the pair. The recursive call deeper(next) yields the optimal score for the remaining elements, and max retains the best total found across all possible pairings.

Edge Cases Handled

  • Empty Input - When nums is empty, size is zero, all becomes zero, and the initial call deeper(0) returns immediately with a score of zero.
  • Odd Number of Elements - The algorithm assumes that the total number of elements is even; however, if an odd length is supplied, the final recursion will reach a state where one element remains unpaired. In that situation, the inner loops find no valid pair, leaving best at zero, and the function returns the accumulated score for the paired subset, effectively ignoring the solitary element.
  • Single Element - With a single element, the loops never find a pair, and the recursion terminates with a score of zero, which is the correct maximum when no pair can be formed.

These conditions are naturally covered by the mask-based termination check and the pair-selection loops without requiring explicit conditional branches.

Performance Optimizations

The implementation incorporates several techniques that reduce the computational burden:

  • Bitmask State Encoding - Representing the selection state as an integer enables constant-time checks (picked & mask) and updates (picked | mask). Bitwise operations are highly efficient compared with list-based state tracking.
  • Precomputed GCD Matrix - By calculating all GCDs once, the inner loop avoids the overhead of invoking the Euclidean algorithm repeatedly. This transforms a potentially quadratic GCD cost into a simple array lookup.
  • Memoization via @cache - Storing the result of each distinct mask eliminates exponential recomputation. Since the number of possible masks is 2^size, the cache ensures each subproblem is solved at most once.
  • Use of bit_count - Leveraging the built-in method to count set bits provides a fast way to determine how many pairs have already been formed, which directly influences the factor multiplier.

Collectively, these optimizations allow the algorithm to explore the full combinatorial space for moderate input sizes while keeping runtime within practical limits.

written by openai gpt

ELI5 - Simplified Explanation

Imagine there is a big pile of numbered cards laid out on a table. The goal of this game is to pick up all the cards by grabbing them two at a time. Every time a pair is picked up, those two numbers get ready to play a game where they look for their secret shared friend, which is the biggest number that both of them can be divided by. This secret friend is multiplied by a score that grows higher and higher as more pairs are taken from the table.

To keep track of which cards are still on the table and which have already been taken, the computer uses a special list of ones and zeros. Think of it like a row of light switches where a light is turned on if the card has been picked up. At the start, all the lights are off.

When the computer looks for the best way to play, it starts a process where it explores every possible way to pair up the cards. It keeps trying different combinations to see which path leads to the biggest total score. Because there are so many ways to pair the cards, the computer remembers the results of the paths it has already checked so it does not have to do the same work again. It carefully checks every single card until the table is empty and all the lights are turned on. By comparing all the different paths, it finds the winning strategy that results in the largest possible number.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 7.38 | σ = 1.21

Complexity Analysis

Time: exponential
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Python Go TS
Progiez C++ Java Python
github black-shadows C++
charles-wangkai Java
everthis JS
fsq C++
haoel C++
JoshCrozier JS
lkwq007 Python
suxrobGM C#
varunu28 Java
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fsq C++
haoel C++
JoshCrozier JavaScript
lkwq007 Python
suxrobGM C#
varunu28 Java
wisdompeak C++
25 links | 14 authors | 7 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

6 solutions   November 4, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality