Most Expensive Item That Can Not Be Bought

Most Expensive Item That Can Not Be Bought

What is this problem about?

The Most Expensive Item That Can Not Be Bought problem is based on the Chicken McNugget theorem (Frobenius coin problem). Given two coprime positive integers a and b, find the largest integer that cannot be expressed as a*x + b*y for non-negative integers x, y. The formula is a*b - a - b. This Most Expensive Item That Can Not Be Bought coding problem combines number theory with dynamic programming.

Why is this asked in interviews?

Amazon asks this to test number theory knowledge — specifically the Frobenius coin problem — combined with DP for the general case (non-coprime or multiple denominations). The math, number theory, and dynamic programming interview pattern is directly applicable, and knowing the closed-form formula vs. the DP approach both demonstrate valuable knowledge.

Algorithmic pattern used

Number theory (closed form) or DP. If gcd(a, b) = 1, the answer is a*b - a - b. For the general DP approach: create a boolean array canBuy[0..limit] where canBuy[i] = True if i can be expressed as a combination. Use a coin-change style DP. The largest index that remains False is the answer.

Example explanation

a=3, b=5. GCD(3,5)=1 → answer = 35-3-5 = 7. Verification: 7 cannot be expressed as 3x+5y (x,y≥0): 30+51=5, 31+50=3, 32+50=6, 30+50=0... 7 is impossible. 8=3+5=31+5*1 ✓.

For general DP: mark all reachable values. Answer = largest unmarked value.

Common mistakes candidates make

• Applying the formula when gcd(a,b) ≠ 1 (formula only valid for coprime pairs).
• DP upper bound too small (must go at least to a*b for two coins).
• Forgetting to initialize canBuy[0] = True.
• Confusing the "cannot be bought" constraint with "can be bought."

Interview preparation tip

The Frobenius coin theorem a*b - a - b is a beautiful result worth memorizing for coprime pairs. For non-coprime or multi-denomination problems, DP coin change is the fallback. In interviews, state the theorem, verify gcd=1, and present both the formula and DP as alternative approaches — this shows mathematical depth. Practice problems involving "representation as linear combinations of integers" to build fluency with Frobenius-type reasoning.