Problem Statement

You are given an array of toy prices and a budget K. Your task is to determine the maximum number of toys you can purchase with the given budget, such that the total cost of the purchased toys does not exceed K.

Examples

Example 1:

Input: arr(Toy Prices) = [1, 2, 3, 4, 5], Budget K = 7

Output: 3

Explanation:

With a budget of 7, you can purchase toys priced at [1, 2, 3], totaling 6, which is within the budget. Therefore, you can purchase a maximum of 3 toys.

Example 2:

Input: arr(Toy Prices) = [2, 4, 6, 8], Budget K = 10

Output: 2

Explanation:

With a budget of 10, you can purchase toys priced at [2, 4], totaling 6, which is within the budget. Therefore, you can purchase a maximum of 2 toys.

Different Approaches

1 Sliding Window Approach

We first sort the toy prices in ascending order. Then, we iterate through the sorted toy prices, adding each toy's price to the total cost until the total cost exceeds the budget K. The number of toys purchased at this point gives us the maximum number of toys that can be purchased within the budget.

Algorithm:

1. Sort the toy prices in ascending order.
2. Initialize a variable totalCost to 0 and a variable toysPurchased to 0.
3. Iterate through the sorted toy prices:
   1. Add the price of the current toy to totalCost.
   2. If totalCost exceeds the budget K, break the loop.
   3. Increment toysPurchased.
4. Return toysPurchased as the result.

Code Implementation in C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxToys(vector<int>& prices, int k) {
    sort(prices.begin(), prices.end());
    int totalCost = 0;
    int toysPurchased = 0;
    
    for (int price : prices) {
        totalCost += price;
        if (totalCost > k) {
            break;
        }
        toysPurchased++;
    }
    
    return toysPurchased;
}

int main() {
    vector<int> prices = {1, 2, 3, 4, 5};
    int budget = 7;
    
    int maxToysPurchased = maxToys(prices, budget);
    cout << "Maximum number of toys that can be purchased with budget " << budget << ": " << maxToysPurchased << endl;
    
    return 0;
}

Complexity Analysis:

Time Complexity:O(n*log n), where n is the size of the cost array.

Space Complexity:O(1)