LeetCode 4050 | Biweekly Contest 191 Q3 | Minimum Days to Score Exactly N Points | Easy DP | C++
Minimum Days to Score Exactly N Points - Video Solution
Watch 2 video solutions for Minimum Days to Score Exactly N Points, a medium level problem. This walkthrough by CodeSprint has 352 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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