Number of Ways to Buy Pens and Pencils - Problem

Math Enumeration Medium

You are given an integer total indicating the amount of money you have. You are also given two integers cost1 and cost2 indicating the price of a pen and pencil respectively.

You can spend part or all of your money to buy multiple quantities (or none) of each kind of writing utensil.

Return the number of distinct ways you can buy some number of pens and pencils.

Input & Output

Example 1 — Basic Case

$ Input: total = 20, cost1 = 1, cost2 = 1

› Output: 231

💡 Note: With $20 and both items costing $1, we can buy 0-20 pens and 0-20 pencils. For 0 pens: 21 pencil options (0-20). For 1 pen: 20 pencil options (0-19). Pattern continues: 21+20+19+...+1 = 231 ways.

Example 2 — Different Costs

$ Input: total = 5, cost1 = 10, cost2 = 10

› Output: 1

💡 Note: Budget is $5 but both items cost $10. Can only afford 0 pens and 0 pencils, so there's only 1 way: buy nothing.

Example 3 — Unequal Costs

$ Input: total = 6, cost1 = 2, cost2 = 3

› Output: 7

💡 Note: 0 pens: can buy 0,1,2 pencils (3 ways). 1 pen ($4 left): can buy 0,1 pencils (2 ways). 2 pens ($2 left): can buy 0 pencils (1 way). 3 pens ($0 left): can buy 0 pencils (1 way). Total: 3+2+1+1 = 7 ways.

Constraints

1 ≤ total, cost1, cost2 ≤ 10⁶

Visualization

Tap to expand

Asked in

M Microsoft 15 a Amazon 12

The key insight is to fix the quantity of one item and mathematically calculate the options for the other. The optimal approach iterates through all possible pen quantities and uses division to find pencil options, achieving O(total) time complexity instead of O(total²).

Common Approaches

✓ Brute Force Enumeration

⏱️ Time: O(total²) Space: O(1)

Iterate through all possible quantities of pens and pencils, checking if each combination's total cost is within budget. Count valid combinations.

Optimized Single Loop

⏱️ Time: O(total) Space: O(1)

For each possible number of pens, calculate the remaining budget and determine how many pencils can be bought. This eliminates the inner loop by using division.

Brute Force Enumeration — Algorithm Steps

Step 1: Try every possible number of pens from 0 to total/cost1
Step 2: For each pen count, try every possible number of pencils from 0 to total/cost2
Step 3: Check if pen_cost + pencil_cost ≤ total, increment counter if valid

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Calculate maximum possible pens and pencils

Double Loop

Try every combination of pens and pencils

Count Valid

Count combinations that fit within budget

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int total, int cost1, int cost2) {
    int count = 0;
    int maxPens = total / cost1;
    int maxPencils = total / cost2;
    
    for (int pens = 0; pens <= maxPens; pens++) {
        for (int pencils = 0; pencils <= maxPencils; pencils++) {
            if (pens * cost1 + pencils * cost2 <= total) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    int total, cost1, cost2;
    scanf("%d", &total);
    scanf("%d", &cost1);
    scanf("%d", &cost2);
    
    int result = solution(total, cost1, cost2);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(total²)

Nested loops iterate up to total/cost1 × total/cost2 times, which is O(total²) in worst case

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Number of Ways to Buy Pens and Pencils - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler