Number of Ways to Buy Pens and Pencils - Practice Coding Problems

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: 9

💡 Note: 0 pens: can buy 0,1,2 pencils (3 ways). 1 pen ($2 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

Understanding the Visualization

Input

Budget and item costs

Process

Find all valid pen-pencil combinations

Output

Total number of distinct ways

Key Takeaway

🎯 Key Insight: Instead of checking every combination, fix the pen quantity and use division to count pencil options instantly

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

Approach	Time	Space	Notes
✓ Optimized Single Loop	O(total)	O(1)	Fix pen quantity, calculate pencil options mathematically
Brute Force Enumeration	O(total²)	O(1)	Try all possible combinations of pens and pencils

Optimized Single Loop — Algorithm Steps

Step 1: Iterate through possible pen quantities from 0 to total/cost1
Step 2: For each pen count, calculate remaining money after buying pens
Step 3: Determine maximum pencils affordable with remaining money using division

Visualization

Tap to expand

Step-by-Step Walkthrough

Fix Pens

Choose number of pens to buy

Calculate Remaining

Find remaining budget after buying pens

Count Pencil Options

Use division to find all valid pencil quantities

Code -

solution.c — C

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

long long solution(int total, int cost1, int cost2) {
    long long count = 0;
    int maxPens = total / cost1;
    
    for (int pens = 0; pens <= maxPens; pens++) {
        int remainingMoney = total - pens * cost1;
        int maxPencils = remainingMoney / cost2;
        count += maxPencils + 1; // +1 to include 0 pencils
    }
    
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(total)

Single loop iterates up to total/cost1 times, which is O(total) in worst case

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables for counting and calculations

✓ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Single Loop — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler