LeetCode 2979 - Most Expensive Item That Can Not Be Bought

LeetCode Problem 2979

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

Solution

Problem Understanding

This problem asks us to determine the largest price that cannot be formed using an unlimited number of coins of two given prime denominations.

We are given two distinct prime numbers, primeOne and primeTwo. Alice has an infinite supply of coins with those exact denominations, and the market contains items of every positive integer price. Alice can buy an item if its price can be expressed as:

$$x = a \cdot primeOne + b \cdot primeTwo$$

where a and b are non-negative integers.

Our goal is to find the maximum positive integer that cannot be represented in this form.

For example, if the denominations are 2 and 5, Alice can buy:

• 2 = 1×2
• 4 = 2×2
• 5 = 1×5
• 6 = 3×2
• 7 = 1×5 + 1×2

However, 1 and 3 cannot be formed. Since 3 is the largest such number, the answer is 3.

The constraints tell us several important things:

• Both numbers are prime and distinct
• 1 < primeOne, primeTwo < 10^4
• primeOne * primeTwo < 10^5

The fact that the inputs are prime is extremely important. Since distinct primes are always coprime, the two denominations have a greatest common divisor of 1. This means there exists a finite largest impossible value, after which every larger number becomes representable.

This property points directly to a well known result in number theory.

Important edge cases include very small primes such as (2, 3), where the answer becomes extremely small, and larger prime pairs near the constraint limit, where a brute-force simulation could become inefficient. Since the problem guarantees distinct primes, we never have to worry about equal denominations or non-coprime inputs.

Approaches

Brute Force Approach

A straightforward solution is to simulate all reachable sums using dynamic programming or breadth-first search.

We could create a boolean array where reachable[x] indicates whether value x can be formed using the given coins. Starting from 0, we repeatedly add primeOne and primeTwo to generate reachable sums.

To determine the largest impossible value, we scan through integers until we find a sufficiently long consecutive range of reachable numbers. Since the coin denominations are coprime, once we encounter enough consecutive reachable numbers, all larger values are guaranteed to be reachable.

This approach is correct because it explicitly computes which sums can be formed. However, it is inefficient because we must search over many numbers and maintain additional memory. Even though the constraints are not huge, the problem admits a much cleaner mathematical solution.

Key Insight

This problem is a direct application of the Frobenius Coin Problem, also called the Chicken McNugget Theorem.

For two coprime positive integers a and b, the largest value that cannot be represented as:

$$a \cdot x + b \cdot y$$

for non-negative integers x and y is:

$$a \times b - a - b$$

Since the problem guarantees that primeOne and primeTwo are distinct primes, they are automatically coprime. Therefore, we can directly apply the formula:

$$\text{answer} = primeOne \times primeTwo - primeOne - primeTwo$$

This gives the result in constant time with no extra memory.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(primeOne × primeTwo)	O(primeOne × primeTwo)	Simulates reachable sums using DP
Optimal	O(1)	O(1)	Uses the Frobenius coin formula

Algorithm Walkthrough

1. Read the two prime denominations, primeOne and primeTwo.
2. Observe that the numbers are distinct primes, which guarantees they are coprime. This matters because the Frobenius theorem only applies when the greatest common divisor equals 1.
3. Apply the mathematical formula for the largest non-representable number:

$$primeOne \times primeTwo - primeOne - primeTwo$$ 4. Return the computed value.

Why it works

The Frobenius Coin Theorem proves that for any two coprime integers a and b, every integer greater than:

$$ab - a - b$$

can be expressed as a non-negative combination of a and b, while that exact value itself cannot. Since distinct primes are always coprime, the theorem applies directly, guaranteeing the returned result is correct.

Python Solution

class Solution:
    def mostExpensiveItem(self, primeOne: int, primeTwo: int) -> int:
        return primeOne * primeTwo - primeOne - primeTwo

The implementation is intentionally simple because the heavy lifting is done by the mathematical observation.

We directly multiply the two prime denominations and subtract both values from the product. Since Python integers automatically handle arbitrary precision, there are no overflow concerns. The constraints are already small enough that even fixed-size integers would be safe.

This implementation exactly follows the algorithm described earlier and runs in constant time.

Go Solution

func mostExpensiveItem(primeOne int, primeTwo int) int {
	return primeOne*primeTwo - primeOne - primeTwo
}

The Go implementation mirrors the Python solution exactly. Since the maximum product is below 10^5, integer overflow is not a concern when using Go's standard int type. No additional data structures or special handling are required.

Worked Examples

Example 1

Input:

primeOne = 2, primeTwo = 5

We apply the formula:

Variable	Value
primeOne * primeTwo	10
10 - primeOne	8
8 - primeTwo	3

Final answer:

3

Verification:

Numbers that cannot be formed are:

1, 3

Every number greater than 3 can be formed using combinations of 2 and 5.

Example 2

Input:

primeOne = 5, primeTwo = 7

We apply the formula:

Variable	Value
primeOne * primeTwo	35
35 - primeOne	30
30 - primeTwo	23

Final answer:

23

Verification:

Non-representable values include:

1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18, 23

Every integer greater than 23 can be represented using 5 and 7.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a few arithmetic operations are performed
Space	O(1)	No additional memory is used

The algorithm performs one multiplication and two subtraction operations, regardless of input size. Since no loops, recursion, or auxiliary data structures are involved, both time and space complexity remain constant.

Test Cases

solution = Solution()

# Provided examples
assert solution.mostExpensiveItem(2, 5) == 3  # Example 1
assert solution.mostExpensiveItem(5, 7) == 23  # Example 2

# Smallest valid distinct primes
assert solution.mostExpensiveItem(2, 3) == 1  # Smallest impossible value

# Consecutive primes
assert solution.mostExpensiveItem(3, 5) == 7  # Typical coprime case
assert solution.mostExpensiveItem(7, 11) == 59  # Medium sized primes

# Larger primes near constraints
assert solution.mostExpensiveItem(97, 997) == 95615  # Large product within limit

# Order should not matter
assert solution.mostExpensiveItem(13, 17) == 191  # Standard order
assert solution.mostExpensiveItem(17, 13) == 191  # Reversed order

# Another random prime pair
assert solution.mostExpensiveItem(11, 19) == 179  # General validation

Test	Why
(2, 5)	Verifies provided example
(5, 7)	Verifies second example
(2, 3)	Smallest valid primes
(3, 5)	Confirms formula on small coprime inputs
(7, 11)	Tests a medium sized case
(97, 997)	Stresses near upper product limit
(13, 17) and (17, 13)	Ensures order independence
(11, 19)	General correctness validation

Edge Cases

Smallest Possible Prime Inputs

The smallest valid pair is (2, 3). A naive implementation might incorrectly assume there are several unreachable values, but in reality only 1 cannot be formed. The formula correctly computes:

$$2 \times 3 - 2 - 3 = 1$$

which matches the expected behavior.

Reversed Input Order

The order of the primes should not affect the result. For example, (13, 17) and (17, 13) must return the same value. Since multiplication and addition are commutative, the formula naturally handles this case without any extra logic.

Large Prime Values Near Constraint Limits

For primes close to the upper bounds, brute-force methods may unnecessarily allocate large arrays or simulate many states. For example, (97, 997) still produces an answer instantly with the formula. Since the implementation only performs arithmetic operations, performance remains constant regardless of input size.