Three Moves
Write a function countTotalMoves that calculates the total ways to reach the last spot in a board using any combination of 1, 2, and 3 jumps.
The input for the function is the length of the board.
You are developing a game where players can move 1, 2, or 3 steps. The board is a straight line, and you want to know the total number of ways you can reach the final spot for any combination of jumps.
When we say "total number of ways", we mean the count of all the possible unique paths you can take to reach the end by jumping 1, 2, or 3 spots from any point.
NOTE: If the board length is 0 or 1, you can assume it is 1 total way in both cases. This is an intentional decision by the interviewer which will allow you to focus on the logic of the solution. With a board length of 0, there is no board at all which is an edge case where the starting and ending location converge, so we'll say the total number of ways for the piece to exist in the game is still 1 which is not performing any jumps. With a board length of 1, the only combination of moves is using the 1-hop option. If we instead said for a board length of 0 that the total moves is 0, it complicates the base cases and doesn't really provide any additional meaning. There is an argument for length 0 to be either 0 or 1 moves with no "right answer", so we are opting for the simpler path.
Breakdown
Approach and test strategy
Count ordered sequences using moves of one, two, or three
Read the approach, boundary cases, and complexity
A path of remaining length n can begin with a move of one, two, or three. Count the smaller suffix problems and add them because their first moves distinguish the groups. A negative remaining length contributes zero; zero remaining length contributes one completed empty sequence. Order matters, so a move of one followed by two differs from two followed by one.
Cases to check
- Negative input returns zero, while zero returns one.
- Lengths one, two, and three return one, two, and four.
- Length four returns seven; a two-move stair recurrence would give a different result.
Cost model
Memoizing or tabulating n nonnegative states takes O(n) work with constant transitions per state. A rolling three-answer implementation can use O(1) auxiliary storage when only the final count is needed. State the supported numeric range.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
A top-down approach is very elegant here. Think how to break this into subproblems and what your base cases would be.
Ensure you handle all cases for negative, zero, and positive board lengths.
There is a lot of repeated work for a brute force recursive solution. These are overlapping subproblems. Find a way to remove this to get a O(n) time and space solution.
Three Moves
Write a function countTotalMoves that calculates the total ways to reach the last spot in a board using any combination of 1, 2, and 3 jumps.
The input for the function is the length of the board.
You are developing a game where players can move 1, 2, or 3 steps. The board is a straight line, and you want to know the total number of ways you can reach the final spot for any combination of jumps.
When we say "total number of ways", we mean the count of all the possible unique paths you can take to reach the end by jumping 1, 2, or 3 spots from any point.
NOTE: If the board length is 0 or 1, you can assume it is 1 total way in both cases. This is an intentional decision by the interviewer which will allow you to focus on the logic of the solution. With a board length of 0, there is no board at all which is an edge case where the starting and ending location converge, so we'll say the total number of ways for the piece to exist in the game is still 1 which is not performing any jumps. With a board length of 1, the only combination of moves is using the 1-hop option. If we instead said for a board length of 0 that the total moves is 0, it complicates the base cases and doesn't really provide any additional meaning. There is an argument for length 0 to be either 0 or 1 moves with no "right answer", so we are opting for the simpler path.