Number of Ways to Buy Pens and Pencils - Video Solutions

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.