LeetCode 3610 - Minimum Number of Primes to Sum to Target

The problem requires us to determine the minimum number of prime numbers from the first m primes whose sum equals n. A multiset is allowed, meaning each prime may be chosen multiple times.

leetcodemediumarraymathdynamic-programmingnumber-theory

LeetCode Problem 3610

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Number Theory

Solution

Problem Understanding

The problem requires us to determine the minimum number of prime numbers from the first m primes whose sum equals n. A multiset is allowed, meaning each prime may be chosen multiple times. The input integers n and m specify the target sum and the number of primes available, respectively. The output is a single integer representing the minimum count of primes that sum to n, or -1 if no combination exists.

Constraints indicate that n and m are both ≤ 1000. Therefore, a solution must handle sums up to 1000 and consider up to the 1000th prime efficiently. Edge cases include n smaller than the smallest prime (2), n exactly equal to a prime, and m large enough to include n itself as a prime. The problem guarantees valid positive integers for n and m.

Approaches

A brute-force approach would attempt every combination of the first m primes to sum to n. This ensures correctness because it checks all possibilities, but the time complexity is exponential in n and m, making it infeasible for n = 1000 and m = 1000.

The optimal approach leverages dynamic programming, treating this as a variation of the unbounded integer knapsack problem. Each prime can be used multiple times, and we aim to minimize the count of items (primes) used to achieve a total of n. By maintaining an array dp where dp[s] is the minimum number of primes summing to s, we can iterate through all primes and update dp efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(m^n) O(n) Enumerates all multisets of primes; infeasible for large n/m
Optimal O(n * m) O(n) Dynamic programming using unbounded knapsack principle

Algorithm Walkthrough

  1. Generate Primes: Generate the first m prime numbers using the Sieve of Eratosthenes or a prime enumeration method. This ensures the prime set is accurate and avoids repeated checks for primality.
  2. Initialize DP Array: Construct an array dp of size n + 1 with all elements initialized to infinity (inf) to represent an unattainable sum. Set dp[0] = 0 because zero primes sum to zero.
  3. Iterate Primes: For each prime p in the first m primes, iterate through s from p to n. Update dp[s] as dp[s] = min(dp[s], dp[s - p] + 1) to reflect using one more prime p.
  4. Check Result: After processing all primes, dp[n] contains the minimum number of primes to reach n. If dp[n] remains infinity, return -1 since no combination is possible.
  5. Return Answer: Otherwise, return dp[n] as the final result.

Why it works: At each step, the DP array maintains the invariant that dp[s] is the minimum number of primes summing to s. Iterating over each prime ensures all combinations are considered, and the min update guarantees the minimal count.

Python Solution

class Solution:
    def minNumberOfPrimes(self, n: int, m: int) -> int:
        def generate_primes(k: int) -> list[int]:
            primes = []
            candidate = 2
            while len(primes) < k:
                is_prime = True
                for p in primes:
                    if p * p > candidate:
                        break
                    if candidate % p == 0:
                        is_prime = False
                        break
                if is_prime:
                    primes.append(candidate)
                candidate += 1
            return primes
        
        primes = generate_primes(m)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for p in primes:
            for s in range(p, n + 1):
                dp[s] = min(dp[s], dp[s - p] + 1)
        
        return dp[n] if dp[n] != float('inf') else -1

This implementation first generates the first m primes using trial division. It initializes the dynamic programming array dp to infinity except for dp[0]. For each prime, it iterates through all sums from the prime up to n, updating the minimal number of primes required. Finally, it returns the result, handling unattainable sums correctly.

Go Solution

func minNumberOfPrimes(n int, m int) int {
    generatePrimes := func(k int) []int {
        primes := []int{}
        candidate := 2
        for len(primes) < k {
            isPrime := true
            for _, p := range primes {
                if p*p > candidate {
                    break
                }
                if candidate%p == 0 {
                    isPrime = false
                    break
                }
            }
            if isPrime {
                primes = append(primes, candidate)
            }
            candidate++
        }
        return primes
    }

    primes := generatePrimes(m)
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = 1<<30 // infinity
    }
    dp[0] = 0

    for _, p := range primes {
        for s := p; s <= n; s++ {
            if dp[s-p]+1 < dp[s] {
                dp[s] = dp[s-p] + 1
            }
        }
    }

    if dp[n] >= 1<<30 {
        return -1
    }
    return dp[n]
}

Go-specific differences include using a large integer (1<<30) to represent infinity and appending to slices instead of dynamic arrays. The logic mirrors the Python solution.

Worked Examples

Example 1: n = 10, m = 2

Primes: [2, 3]

s dp[s] update steps
2 min(inf, dp[0]+1)=1
3 min(inf, dp[0]+1)=1
4 min(inf, dp[2]+1)=2
5 min(inf, dp[2]+1)=2, min(2, dp[2]+1)=2
6 min(inf, dp[4]+1)=3, min(3, dp[3]+1)=2
... ...
10 min(inf, dp[8]+1)=4, min(4, dp[7]+1)=4

Result: dp[10]=4

Example 2: n = 15, m = 5

Primes: [2, 3, 5, 7, 11]

dp[15] updated via dp[10]+1 (using prime 5) results in 3.

Example 3: n = 7, m = 6

Primes: [2, 3, 5, 7, 11, 13]

dp[7] updated directly via prime 7 → 1.

Complexity Analysis

Measure Complexity Explanation
Time O(n * m) Each prime iterates through all sums up to n.
Space O(n) DP array of size n + 1.

This is efficient given n ≤ 1000 and m ≤ 1000.

Test Cases

# Provided examples
assert Solution().minNumberOfPrimes(10, 2) == 4  # sum = 10, primes=[2,3]
assert Solution().minNumberOfPrimes(15, 5) == 3  # sum = 15, primes=[2,3,5,7,11]
assert Solution().minNumberOfPrimes(7, 6) == 1   # sum = 7, primes=[2,3,5,7,11,13]

# Edge cases
assert Solution().minNumberOfPrimes(1, 1) == -1  # n smaller than smallest prime
assert Solution().minNumberOfPrimes(2, 1) == 1   # n equals smallest prime
assert Solution().minNumberOfPrimes(1000, 1000) >= 1  # large n, m
Test Why
n smaller than smallest prime Ensures impossibility is handled
n equals a prime Ensures direct solution is detected
large n, m Tests performance and correctness under constraints

Edge Cases

The first edge case occurs when n is smaller than the smallest prime (n = 1). A naive algorithm might attempt to select primes regardless of size, but our DP initialization correctly returns -1.

The second edge case is when n itself is a prime within the first m primes. The DP array ensures that dp[n] is immediately updated to 1, providing the minimal answer without further iterations.

The third edge case involves large inputs, such as n = 1000 and m = 1000. Here, computational efficiency is critical. By limiting the DP array size to `n