Leetcode 2240: Number of Ways to Buy Pens and Pencils

Input: An integer total representing your total budget, and two integers cost1 and cost2 representing the cost of a pen and a pencil respectively.

Example: Input: total = 15, cost1 = 6, cost2 = 4

Constraints:

• 1 <= total, cost1, cost2 <= 10^6

Output: Return the number of distinct ways to buy pens and pencils while not exceeding the total budget.

Example: Output: 7

Constraints:

• The output must be a single integer representing the number of valid combinations.

Goal: Calculate the number of distinct ways to purchase pens and pencils such that the total cost is less than or equal to the budget.

Steps:

• 1. Iterate over the number of pens that can be purchased, ranging from 0 to total/cost1.

• 2. For each number of pens, calculate the remaining budget after buying the pens.

• 3. Determine the maximum number of pencils that can be purchased within the remaining budget.

• 4. Accumulate the total number of valid combinations.

Goal: The total budget and the costs of pens and pencils are positive integers within the given range.

Steps:

• 1 <= total, cost1, cost2 <= 10^6

Assumptions:

• At least one valid combination is possible, even if it means buying nothing.

• The costs of pens and pencils are not necessarily multiples of each other.

• Input: Input: total = 15, cost1 = 6, cost2 = 4

• Explanation: You can buy 0 pens and 0-3 pencils (4 ways), 1 pen and 0-1 pencils (2 ways), or 2 pens and 0 pencils (1 way). Total: 4 + 2 + 1 = 7.

• Input: Input: total = 7, cost1 = 3, cost2 = 4

• Explanation: You can buy 0 pens and 0-1 pencils (2 ways) or 1 pen and 0 pencils (1 way). Total: 2 + 1 = 3.

Approach: Use a simple loop to iterate through possible purchases of pens and calculate the corresponding combinations for pencils.

Observations:

• The problem can be broken into two nested loops: the outer loop iterates over the possible numbers of pens, and the inner logic calculates the maximum number of pencils for the remaining budget.

• Each iteration of the loop corresponds to a possible number of pens.

• Using a single loop is possible because we only calculate the maximum number of pencils for a given budget.

Steps:

• 1. Initialize a counter to track the number of valid combinations.

• 2. Iterate over the possible number of pens from 0 to total/cost1.

• 3. For each number of pens, compute the remaining budget.

• 4. Calculate the number of pencils that can be purchased with the remaining budget.

• 5. Add the number of valid combinations for the current iteration to the counter.

• 6. Return the total count.

Empty Inputs:

• Not applicable, as the inputs are always positive integers.

Large Inputs:

• total = 10^6, cost1 = 1, cost2 = 2

Special Values:

• cost1 or cost2 is greater than total, e.g., total = 5, cost1 = 10, cost2 = 3.

Constraints:

• Ensure calculations do not overflow for large inputs within the given constraints.

long long waysToBuyPensPencils(int total, int cost1, int cost2) {
    long long cnt = 0;
    int sum = total;
    while(sum >= 0 || sum/cost2 > 0) {
        cnt+= (sum/cost2 + 1);
        sum -= cost1;
    }
    return cnt;
}

1 : Function Definition

long long waysToBuyPensPencils(int total, int cost1, int cost2) {

This is the function definition for 'waysToBuyPensPencils', which takes three parameters: total money, cost of a pen, and cost of a pencil. It returns a long long value representing the total number of items that can be bought.

2 : Variable Initialization

    long long cnt = 0;

This initializes the variable 'cnt' to store the total number of pens and pencils that can be bought.

3 : Setting Initial Sum

    int sum = total;

This sets the 'sum' variable to the total amount of money available for purchase.

4 : Loop for Buying Items

    while(sum >= 0 || sum/cost2 > 0) {

This while loop continues as long as there is enough money to buy at least one pencil (based on the cost of a pencil).

5 : Counting Possible Purchases

        cnt+= (sum/cost2 + 1);

This line calculates the maximum number of pencils that can be bought with the current 'sum' and adds it to the 'cnt' variable.

6 : Reducing Total Money

        sum -= cost1;

This subtracts the cost of one pen from 'sum', reducing the available money after each purchase.

7 : Returning Result

    return cnt;

This returns the total count of pens and pencils that can be bought with the available money.

Best Case: O(total/cost1)

Average Case: O(total/cost1)

Worst Case: O(total/cost1)

Description: The time complexity is proportional to the number of iterations for possible pen purchases.

Best Case: O(1)

Worst Case: O(1)

Description: Only a few variables are used for tracking state, making space usage constant.

Leetcode 2240: Number of Ways to Buy Pens and Pencils

Explore →