EasyDpAI interview only
Count Ways to Reach Score With 3 5 10
Asked atamazonmicrosoftgoldman-sachs
01 · Problem
In a game, every move scores either 3, 5, or 10 points. Given a target score n, return the number of distinct combinations of moves whose points add up to exactly n.
Order does not matter: 3 + 5 and 5 + 3 are the same combination. If n cannot be reached, return 0.
02 · Examples
Example 01
Input
n = 8
Output
1
The only combination is 3 + 5.
Example 02
Input
n = 13
Output
2
The combinations are 3 + 10 and 3 + 5 + 5.
Example 03
Input
n = 20
Output
4
The combinations are 10 + 10, 5 + 5 + 10, 5 + 5 + 5 + 5, and 3 + 3 + 3 + 3 + 3 + 5.
03 · Constraints
- 011 <= n <= 1000
- 02Each move scores exactly 3, 5 or 10 points
- 03The answer fits in a 64-bit signed integer
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.