FastPrep
Problem · Array

Souvenir Shop Purchases

Learn this problem
● MediumAmazonINTERNOA
See Amazon hiring insights

Problem statement

In an Amazon Souvenir Shop, a shopper visited a souvenir shop with items arranged on the shelf from left to right. The goal is to purchase as many items as possible within a given budget. Notably, the cost of each souvenir increases with each purchase.

Formally, given an array cost of size n, representing the initial cost of each item in the souvenir shop, and m representing the initial amount of money that the shopper has.

The first time a souvenir is bought its cost will be cost[i], the second time it will be 2 * cost[i], the third time it will be 3 * cost[i], and the jth time it will cost j * cost[i], and so on.

The shopper will buy items one by one from left to right, and when she reaches the last item she will go back to the start and repeat this operation until she runs out of money.

What is the number of items that the shopper will buy before she runs out of money?

Function

countPurchasedItems(cost: int[], m: long) → long

Examples

Example 1

cost = [2, 5, 1, 1]m = 18return = 5

Assuming 1-based indexing of the cost array:

  1. Buy item 1 for 2. Remaining money: 18 - 2 = 16. New costs: [4, 5, 1, 1].
  2. Buy item 2 for 5. Remaining money: 16 - 5 = 11. New costs: [4, 10, 1, 1].
  3. Buy item 3 for 1. Remaining money: 11 - 1 = 10. New costs: [4, 10, 2, 1].
  4. Buy item 4 for 1. Remaining money: 10 - 1 = 9. New costs: [4, 10, 2, 2].
  5. Buy item 1 for 4. Remaining money: 9 - 4 = 5. New costs: [6, 10, 2, 2].

The next item would be item 2, which now costs 10, but only 5 money remains. Therefore, the shopper buys 5 items.

Source note (June 28, 2026): The original source image did not include the output for this example. FastPrep worked it out from the problem statement and the given input. If you have the original output or notice something wrong, please let us know and we'll fix it. If we find a fuller source later, we'll come back and update this too. 🐥

More Amazon problems

drafts saved locally
public long countPurchasedItems(int[] cost, long m) {
  // write your code here
}
cost[2, 5, 1, 1]
m18
expected5
checking account