Find the most expensive item that can not be bought
Given two distinct prime numbers, p1 and p2. Alice wants to buy a gift for Bob from a market that sells items priced at every positive integer. Alice has unlimited coins of denominations p1 and p2. The task is to find the highest price of an item that Alice cannot afford to buy for Bob.
Example:
Input: p1 = 2, p2 = 5
Output: 3
Explanation: The prices that Alice cannot buy are 1 and 3. This is because 1 cannot be expressed as a linear combination of 2 and 5 using non-negative integers, and 3 is the largest such price.Input: p1 = 5, p2 = 7
Output: 23
Explanation: The prices that Alice cannot buy are 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18, and 23. This is because these prices cannot be expressed as a linear combination of 5 and 7 using non-negative integers. The most expensive price that Alice cannot buy is 23.
Approach:
It’s clear that if an item costs p1 or p2 we can buy it. Similarly, we can also buy an item that costs i % p1 == 0 and i % p2 == 0. Also, if we can buy an i item, we can also buy i + p1 and i + p2. Consequently, we can buy any item > p1 * p2. Create a dp vector up to p1 * p2 and fill with the mentioned rules. Keep track of the maximum item we cannot buy and return it.
Steps-by-step approach:
- Iterates through the range [1, total] to check each possible cost.
- For each iteration:
- Checks if the current number is divisible by either p1 or p2. If so, marks it as a possible cost by setting the corresponding element in the dp vector to true.
- Checks if adding p1 or p2 to the current number is still within the total range. If so, marks these sums as possible costs by setting their corresponding elements in the dp vector to true.
- Updates the res variable to the current number if it’s not possible to make from the given prime numbers.
- For each iteration:
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
int mostExpensiveItem(int primeOne, int primeTwo)
{
// Calculate the total cost of the item
int total = primeOne * primeTwo;
// Initialize a boolean vector 'dp' of size 'total + 1'
// to keep track of the possible costs that can be made
// using the two prime numbers
vector<bool> dp(total + 1, false);
// Initialize the result variable 'res' to keep track of
// the most expensive item
int res = 0;
// Iterate through the range [1, total]
for (int i = 1; i <= total; ++i) {
// If the current number 'i' is divisible by either
// 'primeOne' or 'primeTwo', set the corresponding
// element in the 'dp' vector to 'true'
if (i % primeOne == 0 || i % primeTwo == 0)
dp[i] = true;
// If the current number 'i' is possible to make and
// adding 'primeOne' to it is still within the
// 'total' range, set the corresponding element in
// the 'dp' vector to 'true'
if (dp[i] && i + primeOne <= total)
dp[i + primeOne] = true;
// If the current number 'i' is possible to make and
// adding 'primeTwo' to it is still within the
// 'total' range, set the corresponding element in
// the 'dp' vector to 'true'
if (dp[i] && i + primeTwo <= total)
dp[i + primeTwo] = true;
// If the current number 'i' is not possible to
// make, update the 'res' variable to the current
// value of 'i'
if (!dp[i])
res = i;
}
// Return the most expensive item that can be made
return res;
}
// Driver code
int main()
{
// Static input
int primeOne = 2;
int primeTwo = 5;
// Call the mostExpensiveItem method with the static
// input
int result = mostExpensiveItem(primeOne, primeTwo);
// Print the result
cout << "The most expensive item that cannot be bought "
"is: "
<< result << endl;
return 0;
}
import java.util.Arrays;
public class Main {
static int mostExpensiveItem(int primeOne, int primeTwo)
{
// Calculate the total cost of the item
int total = primeOne * primeTwo;
// Initialize a boolean array 'dp' of size 'total +
// 1' to keep track of the possible costs that can
// be made using the two prime numbers
boolean[] dp = new boolean[total + 1];
// Initialize the result variable 'res' to keep
// track of the most expensive item
int res = 0;
// Iterate through the range [1, total]
for (int i = 1; i <= total; ++i) {
// If the current number 'i' is divisible by
// either 'primeOne' or 'primeTwo', set the
// corresponding element in the 'dp' array to
// 'true'
if (i % primeOne == 0 || i % primeTwo == 0)
dp[i] = true;
// If the current number 'i' is possible to make
// and adding 'primeOne' to it is still within
// the 'total' range, set the corresponding
// element in the 'dp' array to 'true'
if (dp[i] && i + primeOne <= total)
dp[i + primeOne] = true;
// If the current number 'i' is possible to make
// and adding 'primeTwo' to it is still within
// the 'total' range, set the corresponding
// element in the 'dp' array to 'true'
if (dp[i] && i + primeTwo <= total)
dp[i + primeTwo] = true;
// If the current number 'i' is not possible to
// make, update the 'res' variable to the
// current value of 'i'
if (!dp[i])
res = i;
}
// Return the most expensive item that can't be
// bought
return res;
}
// Driver code
public static void main(String[] args)
{
// Static input
int primeOne = 2;
int primeTwo = 5;
// Call the mostExpensiveItem method with the static
// input
int result = mostExpensiveItem(primeOne, primeTwo);
// Print the result
System.out.println(
"The most expensive item that cannot be bought is: "
+ result);
}
}
// This code is contributed by shivamgupta310570
def most_expensive_item(prime_one, prime_two):
# Calculate the total cost of the item
total = prime_one * prime_two
# Initialize a boolean list 'dp' of size 'total + 1'
# to keep track of the possible costs that can be made
# using the two prime numbers
dp = [False] * (total + 1)
# Initialize the result variable 'res' to keep track of
# the most expensive item
res = 0
# Iterate through the range [1, total]
for i in range(1, total + 1):
# If the current number 'i' is divisible by either
# 'prime_one' or 'prime_two', set the corresponding
# element in the 'dp' list to 'True'
if i % prime_one == 0 or i % prime_two == 0:
dp[i] = True
# If the current number 'i' is possible to make and
# adding 'prime_one' to it is still within the
# 'total' range, set the corresponding element in
# the 'dp' list to 'True'
if dp[i] and i + prime_one <= total:
dp[i + prime_one] = True
# If the current number 'i' is possible to make and
# adding 'prime_two' to it is still within the
# 'total' range, set the corresponding element in
# the 'dp' list to 'True'
if dp[i] and i + prime_two <= total:
dp[i + prime_two] = True
# If the current number 'i' is not possible to
# make, update the 'res' variable to the current
# value of 'i'
if not dp[i]:
res = i
# Return the most expensive item that can be made
return res
# Driver code
if __name__ == "__main__":
# Static input
prime_one = 2
prime_two = 5
# Call the most_expensive_item function with the static
# input
result = most_expensive_item(prime_one, prime_two)
# Print the result
print("The most expensive item that cannot be bought is:", result)
# This code is contributed by Ayush Mishra
function mostExpensiveItem(primeOne, primeTwo) {
// Calculate the total cost of the item
const total = primeOne * primeTwo;
// Initialize an array 'dp' of size 'total + 1' to keep track
// of the possible costs that can be made using the two prime numbers
const dp = new Array(total + 1).fill(false);
// Initialize the result variable 'res' to keep track of the most expensive item
let res = 0;
// Iterate through the range [1, total]
for (let i = 1; i <= total; ++i) {
// If the current number 'i' is divisible by either 'primeOne' or 'primeTwo',
// set the corresponding element in the 'dp' array to 'true'
if (i % primeOne === 0 || i % primeTwo === 0)
dp[i] = true;
// If the current number 'i' is possible to make and adding 'primeOne' to it
// is still within the 'total' range, set the corresponding element in the 'dp'
//array to 'true'
if (dp[i] && i + primeOne <= total)
dp[i + primeOne] = true;
// If the current number 'i' is possible to make and adding 'primeTwo' to it
// is still within the 'total' range, set the corresponding
//element in the 'dp' array to 'true'
if (dp[i] && i + primeTwo <= total)
dp[i + primeTwo] = true;
// If the current number 'i' is not possible to make, update the 'res' variable
//to the current value of 'i'
if (!dp[i])
res = i;
}
// Return the most expensive item that can't be bought
return res;
}
// Driver code
function main() {
// Static input
const primeOne = 2;
const primeTwo = 5;
// Call the mostExpensiveItem method with the static input
const result = mostExpensiveItem(primeOne, primeTwo);
// Print the result
console.log("The most expensive item that cannot be bought is: " + result);
}
main();
Output
The most expensive item that cannot be bought is: 3
Time Complexity: O(n), where n is p1 * p2
Auxiliary Space: O(n)