Most Expensive Item That Can Not Be Bought

Problem

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 themost expensive item which Alice can not gift to Bob.

Examples

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 < 10^4
• primeOne, primeTwo are prime numbers.
• primeOne * primeTwo < 10^5

Solution

Method 1 - Number Theory (Frobenius Number)

Intuition

This is a classic coin problem: with two coprime denominations (distinct primes), the largest number that cannot be formed is primeOne * primeTwo - primeOne - primeTwo (Frobenius number). All numbers greater than this can be formed.

Approach

Return primeOne * primeTwo - primeOne - primeTwo.

Code

Java

class Solution {
    public int mostExpensiveItem(int primeOne, int primeTwo) {
        return primeOne * primeTwo - primeOne - primeTwo;
    }
}

Python

def mostExpensiveItem(primeOne, primeTwo):
    return primeOne * primeTwo - primeOne - primeTwo

Complexity

• ⏰ Time complexity: O(1) — Direct formula.
• 🧺 Space complexity: O(1) — No extra space used.