Skip to the content

Use it or lose it

Problem

Hannah walks in with 255 in store credit that expires today: whatever she doesn't spend, she loses. She isn't looking for anything in particular. She wants to leave as little of the credit unspent as she can, without going over it and without paying anything out of pocket.

The rules of the credit: different products, one unit of each at most, and only what's in stock today. Spending exactly 255 is fine too.

Grabbing the most expensive thing that still fits, over and over, sounds like the sensible move, but it leaves 6.1 unspent. She can leave less. Show a single row with two columns: what she takes home and then what it adds up to. What she takes home goes in one cell, with the names separated by a comma and a space and listed by id, lowest first, like Mouse, Tablet. The sum is rounded to 2 decimals.

What it has to return

These rows, in any order

itemsspent
Keyboard, Mouse, Monitor254.4

This is what comes out with the data in the practice database this challenge uses. The column names don’t count, so name yours however you like: what counts is how many there are and the order they come in. Besides this one, the challenge has hidden tests with other data that are revealed when you submit your solution.

You start with this

SQL

SELECT id, name, price
FROM products
WHERE stock > 0
  AND price <= 255
ORDER BY price DESC
Solve this challenge

It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.

More O(2ⁿ) challenges

See all challenges →