Combinations to Score N Runs
Filed under Oracle
Free read 2 of 3If the last move is 1, the previous total score was n-1. If the last move is 2, the move before it must have been 1, meaning the total score before (1, 2) was n-3.
The question
Given an integer `n` representing the target number of runs to score, calculate the total number of unique combinations to reach exactly `n` runs. In each move, a player can score either 1 run or 2 runs, with the restriction that 2 runs cannot be scored on two consecutive moves.
Constraints
- 1 <= n <= 45
- Consecutive 2s are forbidden in any valid combination
Examples
- Input
- n = 3
- Output
- 3
- Why
- The valid sequences of runs are [1, 1, 1], [2, 1], and [1, 2]. Note that [2, 2] is invalid.
Approach
If the last move is 1, the previous total score was n-1. If the last move is 2, the move before it must have been 1, meaning the total score before (1, 2) was n-3.
Define total(n) = total(n-1) + total(n-3) for n >= 3, with base cases total(0)=1, total(1)=1, and total(2)=2.
Maintain only the last three state values in variables to compute total(n) in O(n) time and O(1) auxiliary space.
Solution
O(n) time, O(1) space
class Solution:
def countCombinations(self, n: int) -> int:
if n == 0 or n == 1:
return 1
if n == 2:
return 2
dp0, dp1, dp2 = 1, 1, 2
for i in range(3, n + 1):
dp3 = dp2 + dp0
dp0, dp1, dp2 = dp1, dp2, dp3
return dp2
Tips
- What they are testing: Test base cases n=1, n=2, and n=3 to ensure correct initialization of dynamic programming states.
- Common mistake: Treating the problem as standard Fibonacci without incorporating the restriction against consecutive 2s.
Related Oracle questions
Collected from public candidate posts and coding forums. Updated Nov 2026.