Skip to main content
Talentd

Most Expensive Item That Can Not Be Bought - Solution & Explanation

MediumPremiumFree on FleetCodeMathDynamic ProgrammingNumber Theory5 min readAsked at: Amazon
Practice this problem

Problem Statement

You are given two distinct prime numbers primeOne and primeTwo.

Alice and Bob are visiting a market. The market has an infinite number of items, for any positive integer x there exists an item whose price is x. Alice wants to buy some items from the market to gift to Bob. She has an infinite number of coins in the denomination primeOne and primeTwo. She wants to know the most expensive item she can not buy to gift to Bob.

Return the price of the most expensive item which Alice can not gift to Bob.

 

Example 1:

Input: primeOne = 2, primeTwo = 5
Output: 3
Explanation: The prices of items which cannot be bought are [1,3]. It can be shown that all items with a price greater than 3 can be bought using a combination of coins of denominations 2 and 5.

Example 2:

Input: primeOne = 5, primeTwo = 7
Output: 23
Explanation: The prices of items which cannot be bought are [1,2,3,4,6,8,9,11,13,16,18,23]. It can be shown that all items with a price greater than 23 can be bought.

 

Constraints:

  • 1 < primeOne, primeTwo < 104
  • primeOne, primeTwo are prime numbers.
  • primeOne * primeTwo < 105

Approach Overview

Problem Overview: You are given two item prices a and b. Any purchase must be formed using non‑negative multiples of these prices. The task is to return the largest total value that cannot be formed exactly using those two prices.

This is a classic number theory problem known as the Frobenius Coin Problem. Because the inputs in this problem are prime numbers, they are guaranteed to be coprime, which enables a direct mathematical solution.

Approach 1: Dynamic Programming / Reachability Simulation (O(a*b) time, O(a*b) space)

The straightforward way is to simulate which totals are reachable. Create a boolean array up to a * b. Start from 0 and repeatedly add a and b. If a value is reachable, mark value + a and value + b as reachable. After filling the table, scan for the largest value that remains unreachable.

This approach works because once numbers exceed a * b, patterns repeat and all sufficiently large values become reachable. While easy to reason about, it wastes time and memory for a problem that has a direct mathematical formula. Still, it helps illustrate the structure of reachable combinations and can be useful when first encountering the Frobenius problem.

Conceptually, this simulation resembles subset-style transitions often seen in dynamic programming, where states represent reachable sums.

Approach 2: Chicken McNugget Theorem (O(1) time, O(1) space)

The optimal solution relies on a classic result from number theory. For two coprime integers a and b, the largest value that cannot be expressed as a*x + b*y (for non‑negative integers x and y) is:

a * b - a - b

This is known as the Chicken McNugget Theorem. Since the problem guarantees prime numbers, gcd(a, b) = 1, so the theorem always applies.

The implementation becomes trivial: compute a * b - a - b and return it. No loops, no data structures, and constant time execution. Problems like this frequently appear in math-heavy interviews where recognizing the underlying theorem saves significant work.

Recommended for interviews: Interviewers expect the mathematical insight. A brute-force or DP explanation shows you understand how reachable sums behave, but recognizing the Chicken McNugget theorem and reducing the problem to a*b - a - b demonstrates strong number theory intuition and leads to the optimal O(1) solution.

Solution

According to the Chicken McNugget Theorem, for two coprime positive integers a and b, the largest number that cannot be expressed as a combination of a and b is ab - a - b.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming ReachabilityO(a*b)O(a*b)Useful for understanding reachable sums or when the theorem is unknown
Chicken McNugget TheoremO(1)O(1)Optimal solution when the two numbers are coprime

Video Solution

Most Expensive Item That Cannot Be Bought • Owen Wu • 30 views views

Frequently Asked Questions

Is Most Expensive Item That Can Not Be Bought easy or hard?
The problem is rated Medium on LeetCode but becomes very easy if you recognize the Chicken McNugget theorem. Without that insight, many candidates attempt dynamic programming or brute-force enumeration, which is significantly less efficient.
Most Expensive Item That Can Not Be Bought Python/Java solution
The implementation is identical across languages: return a*b - a - b. In Python, Java, C++, Go, or TypeScript, compute the product of the two inputs and subtract both numbers to obtain the largest unreachable value.
How to solve Most Expensive Item That Can Not Be Bought in O(1)?
Use the Chicken McNugget theorem. If two item prices are a and b and gcd(a, b) = 1, the largest unreachable value is a*b - a - b. The implementation simply returns that expression, which eliminates the need for loops or dynamic programming.
What is the best approach for Most Expensive Item That Can Not Be Bought?
The optimal approach uses the Chicken McNugget theorem from number theory. For two coprime integers a and b, the largest value that cannot be formed using a*x + b*y is a*b - a - b. Since the problem guarantees prime numbers, they are coprime, so the answer can be computed in O(1) time with a simple formula.
Is Most Expensive Item That Can Not Be Bought asked at Google/Amazon/Meta?
Problems based on the Frobenius coin problem and number theory formulas appear in interviews at companies like Google and Amazon, especially for candidates expected to recognize mathematical patterns. The exact LeetCode problem may vary, but the concept is commonly tested.
What data structure is used in Most Expensive Item That Can Not Be Bought?
The optimal solution does not require any data structures because it relies on a mathematical formula. A learning-oriented approach may use a boolean array or set to track reachable sums, which resembles dynamic programming state tracking.
What is the time complexity of Most Expensive Item That Can Not Be Bought?
The optimal solution runs in O(1) time and O(1) space because it directly computes a*b - a - b using a mathematical formula. A brute-force or dynamic programming approach that checks reachable sums would take O(a*b) time and space.

Ready to solve this problem?

Practice Most Expensive Item That Can Not Be Bought with our built-in code editor and test cases.

Practice on FleetCode
Previous

Coin Change

Next

Minimum Cost For Tickets