Harry Potter Discounts: A Code Challenge Algorithm

This is one of my favorite code katas. A bookshop sells 5 Harry Potter books at 8 EUR each. Buy different titles together and you get a discount:

• 2 different books: 5% off
• 3 different books: 10% off
• 4 different books: 20% off
• 5 different books: 25% off

Duplicates don't count toward the discount. The challenge: calculate the minimum price for any basket.

Why It's Tricky

The greedy approach — always make the biggest group possible — doesn't work.

Example: 2 copies each of books 1-4, plus 2 copies each of book 5. Greedy takes a group of 5 and a group of 3. But two groups of 4 is actually cheaper. The 20% discount on groups of 4 beats the combination of 25% on 5 and 10% on 3.

This is a problem where greedy looks right but isn't.

The Solution

Use a greedy approach, but convert sets of (5 + 3) into (4 + 4) whenever possible.

function calculatePrice(books) {
  const discounts = [0, 0, 0.05, 0.10, 0.20, 0.25];
  const PRICE = 8;

  const counts = [0, 0, 0, 0, 0];
  for (const book of books) {
    counts[book - 1]++;
  }

  const groups = [0, 0, 0, 0, 0, 0]; // groups[i] = number of groups of size i

  while (true) {
    const available = counts.filter(c => c > 0).length;
    if (available === 0) break;

    counts.sort((a, b) => b - a);
    for (let i = 0; i < available; i++) {
      counts[i]--;
    }
    groups[available]++;
  }

  // optimize: convert (5 + 3) pairs into (4 + 4)
  const convertible = Math.min(groups[5], groups[3]);
  groups[5] -= convertible;
  groups[3] -= convertible;
  groups[4] += convertible * 2;

  let total = 0;
  for (let size = 1; size <= 5; size++) {
    total += groups[size] * size * PRICE * (1 - discounts[size]);
  }

  return total;
}

console.log(calculatePrice([1, 2, 3, 4, 5, 1, 2, 3])); // 51.20
console.log(calculatePrice([1, 1, 2, 2, 3, 3, 4, 5])); // 51.20

Complexity

• Time: O(n) where n is the total number of books.
• Space: O(1) — fixed-size arrays.

The Trade-off

This optimized greedy solution handles the known edge cases and gives the correct minimum price. A full dynamic programming approach would handle arbitrary discount structures, but for this specific problem with 5 books and fixed discount tiers, the greedy-with-correction approach is simpler and fast enough.