Number of Ways to Buy Pens and Pencils solution and explanation
6 more videos on this problem
2240. Number of Ways to Buy Pens and Pencils || Leetcode BiWeekly Contest 76 || Leetcode 2240Bro Coders · 6:57 · 1K views
2240. Number of Ways to Buy Pens and Pencils (Leetcode Medium)Programming Live with Larry · 6:03 · 694 views
2240. Number of Ways to Buy Pens and Pencils | LeetCode Biweekly 76 Leetcode Medium | LeetcodeBinaryMagic · 7:13 · 383 views
Leetcode Biweekly contest 76 - Number of Ways to Buy Pens and PencilsPrakhar Agrawal · 4:21 · 294 views
Number of Ways to Buy Pens and Pencils | LeetCode 2240 | C++DLG_Coding · 11:20 · 212 views
Number of Ways to Buy Pens and Pencils - LeetCode 2240 - Java Solutionalgobest - Computer Science · 2:39 · 127 views
Number of Ways to Buy Pens and Pencils | Leetcode 2240 | Approach + Code with explanation.Pirai's Academy · 8:12 · 83 views
The problem
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.
Example 1:
Input: total = 20, cost1 = 10, cost2 = 5 Output: 9 Explanation: The price of a pen is 10 and the price of a pencil is 5. - If you buy 0 pens, you can buy 0, 1, 2, 3, or 4 pencils. - If you buy 1 pen, you can buy 0, 1, or 2 pencils. - If you buy 2 pens, you cannot buy any pencils. The total number of ways to buy pens and pencils is 5 + 3 + 1 = 9.
Example 2:
Input: total = 5, cost1 = 10, cost2 = 10 Output: 1 Explanation: The price of both pens and pencils are 10, which cost more than total, so you cannot buy any writing utensils. Therefore, there is only 1 way: buy 0 pens and 0 pencils.
Constraints:
1 <= total, cost1, cost2 <= 106
Approach overview
Problem Overview: You are given a total budget and the cost of a pen and a pencil. The task is to count how many different combinations of pens and pencils you can buy without exceeding the total amount. Any combination where the total cost is less than or equal to the budget is valid.
Approach 1: Brute Force Enumeration (Time: O((total/cost1) * (total/cost2)), Space: O(1))
The most direct solution enumerates every possible pair of pen and pencil counts. Iterate the number of pens from 0 to total / cost1. For each value, iterate the number of pencils from 0 to total / cost2 and check whether the combined cost stays within the budget. Each valid pair contributes one to the total count. This approach is straightforward and mirrors the problem statement, but the nested iteration becomes inefficient when the budget is large.
This method uses pure enumeration and basic arithmetic checks. It does not require additional data structures, so the space complexity stays constant. However, the time complexity grows quickly because every possible pair is tested. Problems involving counting combinations often start with this brute-force strategy before optimizing using insights from math or enumeration.
Approach 2: Mathematical Enumeration (Time: O(total/cost1), Space: O(1))
A more efficient approach avoids the inner loop entirely. Iterate the number of pens from 0 to total / cost1. For each choice of pens, compute the remaining budget as remaining = total - pens * cost1. The number of pencils you can buy is simply remaining / cost2. Since you can choose any pencil count from 0 up to that value, the number of valid combinations for this pen count is (remaining / cost2) + 1.
Add this value to the result for every possible pen count. This works because the pencil choices form a continuous range of valid values. Instead of checking each pair individually, you count all valid pencil options in constant time using integer division. The algorithm effectively enumerates only one dimension and derives the other mathematically.
This technique appears frequently in counting problems where one variable determines the remaining constraint for another variable. Recognizing this pattern turns a quadratic brute-force search into a linear scan based on simple arithmetic.
Recommended for interviews: The mathematical enumeration approach is what interviewers expect. Writing the brute-force solution first demonstrates that you understand the problem space. Then reducing the nested loop to a single loop using a formula shows stronger algorithmic reasoning and familiarity with optimization patterns common in counting and math-based problems.
Approach 1: Brute Force Approach
In the brute force approach, we will iterate through possible numbers of pens starting from 0. For each feasible number of pens, we will calculate the leftover money and determine how many pencils we can buy with that remaining amount. We then sum the possibilities to get the total number of ways.
def number_of_ways(total, cost1, cost2):
count = 0
for pens in range(total // cost1 + 1):
remaining = total - pens * cost1
count += (remaining // cost2) + 1
return count
print(number_of_ways(20, 10, 5)) # Output: 9
print(number_of_ways(5, 10, 10)) # Output: 1public class Main {
public static int numberOfWays(int total, int cost1, int cost2) {
int count = 0;
for (int pens = 0; pens * cost1 <= total; pens++) {
int remaining = total - pens * cost1;
count += (remaining / cost2) + 1;
}
return count;
}
public static void main(String[] args) {
System.out.println(numberOfWays(20, 10, 5)); // Output: 9
System.out.println(numberOfWays(5, 10, 10)); // Output: 1
}
}#include <iostream>
using namespace std;
int numberOfWays(int total, int cost1, int cost2) {
int count = 0;
for (int pens = 0; pens * cost1 <= total; ++pens) {
int remaining = total - pens * cost1;
count += (remaining / cost2) + 1;
}
return count;
}
int main() {
cout << numberOfWays(20, 10, 5) << endl; // Output: 9
cout << numberOfWays(5, 10, 10) << endl; // Output: 1
return 0;
}function numberOfWays(total, cost1, cost2) {
let count = 0;
for (let pens = 0; pens * cost1 <= total; pens++) {
let remaining = total - pens * cost1;
count += Math.floor(remaining / cost2) + 1;
}
return count;
}
console.log(numberOfWays(20, 10, 5)); // Output: 9
console.log(numberOfWays(5, 10, 10)); // Output: 1;#include <stdio.h>
int numberOfWays(int total, int cost1, int cost2) {
int count = 0;
for (int pens = 0; pens * cost1 <= total; ++pens) {
int remaining = total - pens * cost1;
count += (remaining / cost2) + 1;
}
return count;
}
int main() {
printf("%d\n", numberOfWays(20, 10, 5)); // Output: 9
printf("%d\n", numberOfWays(5, 10, 10)); // Output: 1
return 0;
}using System;
public class Program {
public static int NumberOfWays(int total, int cost1, int cost2) {
int count = 0;
for (int pens = 0; pens * cost1 <= total; pens++) {
int remaining = total - pens * cost1;
count += (remaining / cost2) + 1;
}
return count;
}
public static void Main() {
Console.WriteLine(NumberOfWays(20, 10, 5)); // Output: 9
Console.WriteLine(NumberOfWays(5, 10, 10)); // Output: 1
}
}In Python, the code iterates over the possible number of pens and calculates the number of ways to buy pencils from the remaining money.
The time complexity is O(total/cost1) and the space complexity is O(1).
Approach 2: Enumeration
We can enumerate the number of pens to buy, denoted as x. For each x, the maximum number of pencils we can buy is \frac{total - x times cost1}{cost2}. The number of ways for each x is this value plus 1. We sum up the number of ways for all x to get the answer.
The time complexity is O(\frac{total}{cost1}), and the space complexity is O(1).
function waysToBuyPensPencils(total: number, cost1: number, cost2: number): number {
let ans = 0;
for (let x = 0; x <= Math.floor(total / cost1); ++x) {
const y = Math.floor((total - x * cost1) / cost2) + 1;
ans += y;
}
return ans;
}func waysToBuyPensPencils(total int, cost1 int, cost2 int) (ans int64) {
for x := 0; x <= total/cost1; x++ {
y := (total-x*cost1)/cost2 + 1
ans += int64(y)
}
return
}impl Solution {
pub fn ways_to_buy_pens_pencils(total: i32, cost1: i32, cost2: i32) -> i64 {
let mut ans: i64 = 0;
for pen in 0..=total / cost1 {
ans += (((total - pen * cost1) / cost2) as i64) + 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(total/cost1) and the space complexity is O(1). |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O((total/cost1) * (total/cost2)) | O(1) | Useful for understanding the problem or very small constraints |
| Mathematical Enumeration | O(total/cost1) | O(1) | Optimal approach for large budgets; avoids nested loops using arithmetic counting |
Frequently asked questions
Is Number of Ways to Buy Pens and Pencils easy or hard?
The problem is typically considered easy to medium difficulty. The brute-force idea is straightforward, but recognizing that the inner loop can be replaced with a mathematical count is the key insight that leads to the optimal solution.
Number of Ways to Buy Pens and Pencils Python/Java solution
In both Python and Java, iterate pens from 0 to total/cost1. For each iteration compute remaining = total - pens * cost1, then add (remaining / cost2) + 1 to the answer. The implementation is only a few lines and runs in O(total/cost1) time with constant memory.
How to solve Number of Ways to Buy Pens and Pencils in O(n)?
Treat the number of pens as the primary variable. For each possible pen count, subtract its cost from the total budget and compute how many pencils fit into the remaining amount. The count of pencil options is (remaining / cost2) + 1. Summing this for every pen value gives the total combinations in O(total/cost1) time.
What is the best approach for Number of Ways to Buy Pens and Pencils?
The best approach is mathematical enumeration. Iterate over the number of pens from 0 to total/cost1, compute the remaining budget, and count how many pencils can be bought using integer division. This avoids a nested loop and runs in O(total/cost1) time with O(1) space.
Is Number of Ways to Buy Pens and Pencils asked at Google/Amazon/Meta?
This problem represents a common counting and mathematical enumeration pattern seen in coding interviews. Variations of budget allocation or item combination counting appear in interviews at companies like Amazon and Google where candidates are expected to derive an arithmetic formula instead of brute force.
What data structure is used in Number of Ways to Buy Pens and Pencils?
No specialized data structure is required. The solution relies on simple arithmetic operations and iteration. The key idea comes from mathematical counting and enumeration rather than arrays, hash maps, or trees.
What is the time complexity of Number of Ways to Buy Pens and Pencils?
The optimal solution runs in O(total/cost1) time because it iterates through possible pen counts only once. Each iteration calculates the valid number of pencil combinations using constant-time arithmetic. Space complexity is O(1) since only a few variables are used.