Minimum Days to Score Exactly N Points solution and explanation
The problem
You are given an integer n representing a target score.
Your score starts at 0, and each day you either earn points or skip.
Points are earned during a streak. On the first day of a streak you earn 1 point, on the second day 2 points, on the third day 3 points, and so on. Skipping a day earns nothing and resets the streak, so the next time you earn points, you start from 1 again.
Return the minimum number of days, including any skipped days, needed to reach a score of exactly n.
Example 1:
Input: n = 2
Output: 3
Explanation:
- Day 1: earn 1 point. Score is 1.
- Day 2: skip, which resets the streak. Earning here would add 2 points and take the score past
n = 2. - Day 3: the streak has reset, so earning gives 1 point. Score is exactly
n = 2in 3 days.
Example 2:
Input: n = 9
Output: 6
Explanation:
- Days 1 to 3: earn 1, 2, and 3 points. Score is
1 + 2 + 3 = 6. - Day 4: skip, which resets the streak.
- Days 5 and 6: earn 1 and 2 points. Score is exactly
6 + 1 + 2 = 9in 6 days.
Example 3:
Input: n = 12
Output: 7
Explanation:
- Days 1 to 3: earn 1, 2, and 3 points. Score is
1 + 2 + 3 = 6. - Day 4: skip, which resets the streak.
- Days 5 to 7: earn 1, 2, and 3 points. Score is exactly
6 + 1 + 2 + 3 = 12in 7 days.
Constraints:
1 <= n <= 105
Approach overview
Problem Overview: You are given a target score N and a set of daily scoring options (e.g., 1, 2, 5 points). Each day you can earn exactly one option. Return the minimum number of days required to accumulate exactly N points, or -1 if impossible. This is a classic unbounded knapsack style problem, often referred to as 'Coin Change' in the context of days.
Why Greedy Fails: A natural first attempt is to always pick the largest possible score. For some sets like [1, 3, 4] and N=6, the greedy choice 4+1+1 takes 3 days, but the optimal is 3+3 in 2 days. Because scoring options are arbitrary, a greedy strategy cannot guarantee minimality. You must consider all combinations, which leads to dynamic programming.
Approach 1: Brute Force Recursion (O(2^N) time, O(N) space)
Use recursion to explore every sequence of daily scores. At each step, subtract a scoring option from the remaining target and recurse. The base case is when remaining equals 0, return 0 days; if it goes negative, discard that path. Since each branch tries K options, the number of nodes grows exponentially. This approach is only viable for N less than 20 because of time explosion, but it's a good way to reason about the problem. Space is O(N) due to the recursion stack.
Approach 2: Top-Down Dynamic Programming with Memoization (O(N*K) time, O(N) space)
Memoization turns the recursive tree into a DAG. Use a dictionary or array memo indexed by the remaining score. For each remaining target, compute the answer as the minimum over all scoring options of 1 + memo[remaining - option]. Because each target from 0 to N is solved only once, the total work is O(N*K). Space is O(N) for the memo plus the recursion stack, which reaches O(N) depth. This approach is easier to code if you already have a recursive solution, but it carries function call overhead.
Approach 3: Bottom-Up Iterative DP (O(N*K) time, O(N) space)
Initialize a DP array of length N+1 with infinity, and set dp[0] = 0. Loop over targets from 1 to N, and for each target, loop over every scoring option. If i - option >= 0, update dp[i] = min(dp[i], dp[i - option] + 1). After filling the array, dp[N] holds the answer, or -1 if it's still infinity. This version avoids recursion and is the most commonly written in interviews. Time is O(N*K), space is O(N). You can even use a 1D array in place, so no extra memory is needed beyond the DP table.
Recommended for interviews: Start by explaining the brute force to show you can model the problem, then immediately move to the bottom-up DP. Interviewers want to see that you recognize overlapping subproblems and can implement an iterative solution. The top-down version is acceptable, but bottom-up is preferred for clarity and to avoid recursion depth issues. State the complexity as O(N*K) time and O(N) space, and mention that if the scoring options count K is constant, the solution runs in O(N) time. This is the answer expected for a medium difficulty problem on FleetCode.
Solution
Thinking
The score is a sum of streaks: a streak of length
jcontributes the triangular numberj(j+1)/2. Consecutive streaks must be separated by a skip that resets the streak; the last streak needs no trailing skip.
n = 10^5rules out day-by-day simulation and searching over partitions. Treat “exactlyipoints” as an unbounded knapsack whose items are streaks and whose cost is the number of days.Set
f[0] = -1and always addj + 1(the extra skip) in the transition. The extra skip on the last streak is cancelled byf[0] = -1, so the answer isf[n].
A streak of j days scores the triangular number s = \frac{j(j+1)}{2}. Two consecutive streaks must be separated by exactly one skipped day that resets the streak, while the last streak needs no extra skip.
Let f[i] be the minimum number of days needed to score exactly i points. Set f[0] = -1 and initialize the remaining entries to +infty. Enumerate the length j of the last streak (with score s):
$
f[i] = min\bigl(f[i],\, f[i - s] + j + 1\bigr)
The j + 1 accounts for the j earning days plus one skip. f[0] = -1 cancels the extra skip on the last streak: if a single streak of length j already scores n, then f[n] = f[0] + j + 1 = j.
Since n \le 10^5, we precompute up to the limit and answer each query in O(1). The largest useful j is about \sqrt{2n}.
The time complexity is O(n times \sqrt{n}) for preprocessing, and the space complexity is O(n). Each query is O(1)$.
mx = 10**5 + 1
f = [inf] * mx
f[0] = -1
for i in range(1, mx):
j = 1
while (s := (1 + j) * j // 2) <= i:
f[i] = min(f[i], f[i - s] + j + 1)
j += 1
class Solution:
def minDays(self, n: int) -> int:
return f[n]class Solution {
private static final int MX = 100001;
private static final int[] f = new int[MX];
static {
Arrays.fill(f, Integer.MAX_VALUE);
f[0] = -1;
for (int i = 1; i < MX; i++) {
for (int j = 1; j * (j + 1) / 2 <= i; j++) {
int s = j * (j + 1) / 2;
f[i] = Math.min(f[i], f[i - s] + j + 1);
}
}
}
public int minDays(int n) {
return f[n];
}
}class Solution {
public:
int minDays(int n) {
static const auto f = [] {
constexpr int mx = 100001;
vector<int> f(mx, INT_MAX);
f[0] = -1;
for (int i = 1; i < mx; i++) {
for (int j = 1; j * (j + 1) / 2 <= i; j++) {
int s = j * (j + 1) / 2;
f[i] = std::min(f[i], f[i - s] + j + 1);
}
}
return f;
}();
return f[n];
}
};const MX = 100001;
const f = new Array<number>(MX).fill(Infinity);
f[0] = -1;
for (let i = 1; i < MX; i++) {
for (let j = 1; (j * (j + 1)) / 2 <= i; j++) {
const s = (j * (j + 1)) / 2;
f[i] = Math.min(f[i], f[i - s] + j + 1);
}
}
function minDays(n: number): number {
return f[n];
}const mx = 100001
var f = func() []int {
f := make([]int, mx)
for i := range f {
f[i] = int(^uint(0) >> 1)
}
f[0] = -1
for i := 1; i < mx; i++ {
for j := 1; j*(j+1)/2 <= i; j++ {
s := j * (j + 1) / 2
f[i] = min(f[i], f[i-s]+j+1)
}
}
return f
}()
func minDays(n int) int {
return f[n]
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(2^N) | O(N) | Only for tiny N, understanding recursive structure |
| Top-Down DP (Memoization) | O(N*K) | O(N) | When recursion is natural and N is moderate |
| Bottom-Up DP | O(N*K) | O(N) | General case, optimal for interviews |
Frequently asked questions
Minimum Days to Score Exactly N Points Python solution
Initialize dp = [float('inf')] * (N+1), set dp[0]=0. For i in range(1, N+1), for score in scores, if i >= score, dp[i] = min(dp[i], dp[i-score] + 1). Return dp[N] if it is finite else -1.
Is Minimum Days to Score Exactly N Points easy or hard?
The problem is rated Medium on FleetCode. It requires knowledge of dynamic programming but no advanced optimizations. With an acceptance rate of 41.6%, it is a typical interview-level DP problem.
How to solve Minimum Days to Score Exactly N Points in O(n)?
If the number of scoring options K is constant, the DP solution is O(N*K) which is effectively O(N). Use a 1D DP array and for each target i, loop over the fixed set of scores. With K fixed, the time complexity is linear in N.
What is the best approach for Minimum Days to Score Exactly N Points?
The best approach is dynamic programming. Use a bottom-up DP array where dp[i] stores the minimum days to score i points. For each i, try every scoring option and take the minimum. This runs in O(N*K) time and O(N) space, which is optimal for this problem.
Is Minimum Days to Score Exactly N Points asked at Google/Amazon/Meta?
This is a classic DP pattern similar to Coin Change, and variations appear in interviews at Google, Amazon, and Meta. The problem tests your ability to recognize overlapping subproblems and implement a 1D DP array efficiently.
What data structure is used in Minimum Days to Score Exactly N Points?
A 1D array is the primary data structure for dynamic programming. It stores the minimum days for each target score. The scoring options are kept in a simple list or array. No other complex data structures are required.
What is the time complexity of Minimum Days to Score Exactly N Points?
The optimal dynamic programming solution runs in O(N*K) time, where N is the target score and K is the number of daily scoring options. Space is O(N) for the DP array. Brute force recursion takes O(2^N) and is not feasible for moderate N.