A person has to cover a distance, He can either walk, roll, or jump, each of these actions covers one unit distance. These actions are represented by: walk: w, roll: r, jump: j. Each person is eligible for the trophy if they meet the following criteria :
- The Person rolled for less than 2 unit distance in total.
- The Person jumped less than 3 consecutive unit distances.
Given an integer n, return the number of possible ways the person will be traveling n distance and be eligible for the trophy. The answer may be very large, so return it modulo 109 + 7.
Examples:
Input: 3
Output: 19
Explanation: There are in total 19 ways to travel the distance by following the rules. These 19 ways are-
- All Walk- WWW,
- Two Walk- WWR, WRW, RWW, WWJ, WJW, JWW,
- One Walk- WJJ, JWJ, JJW, WJR, WRJ, RWJ, RJW, JWR, JRW,
- Zero Walk- JJR, JRJ, RJJ
Input: 5
Output: 94
Explanation: There are in total 94 ways to travel the distance by following the rules.Input: 7
Output: 418
Explanation: There are in total 418 ways to travel the distance by following the rules.
Approach: To solve the problem follow the below idea:
- int ‘solver(int n, int roll ,int jump)’: This is a recursive function that calculates the number of valid sequences of rolls, walks and jumps given the current state of steps, total rolls, and consecutive jumps.
- int w = solver(n-1, roll, 0): If the player walks (no rolling or jumping), total roll remains as it is and consecutive jump is reset to 0.
- int r = solver(n-1,roll+1, 0): If the player chooses to roll, total roll is incremented by 1, and consecutive jump is reset to 0.
- int j = solver(n-1, roll, jump+1): If the player chooses to jump, total roll remains the same, and consecutive jump is incremented by 1.
- To handle consecutive jumps, we need to ensure that the jump variable is incremented only in a single function call (only when the person jumps), and resets to zero in all other function calls. This way, we’re specifically tracking the consecutive jumps without introducing additional variations.
- This approach allows us to distinguish between scenarios where jumps are consecutive versus when they are not. It ensures that we’re addressing the specific case of consecutive jumps without introducing complexities related to total jumps across multiple calls. This way, we maintain a clear focus on handling consecutive jumps, which is the intended objective of the code.
- if (jump >= 3 or roll >= 2) return 0; – If there are three or more consecutive jumps (jump >= 3) or two or more consecutive rolls (roll >= 2), then the sequence is not considered valid, so it returns 0.
- if(n == 0) return 1; – If n reaches 0, it means we have successfully completed the sequence, so it returns 1 (indicating one valid sequence).
Below is the implementation of the above approach:
C++14
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;long long int mod = 1e9 + 7;long long int dp[100001][2][3];// dp[i][j][k] = Number of ways to travel// distance i, with j total rolls provided// that the person has jumped// consecutively for the last k times// Function to solve the problemint solver(int n, int roll, int jump){ // Base Cases: If there are more than 3 jumps // or 2 rolls, return 0 (no valid sequence) if (jump >= 3 or roll >= 2) { return 0; } // Base Case: If there are no more steps left, // return 1 (a valid sequence is completed) if (n == 0) return 1; // Memoization: If the solution for this // state is already calculated, return it if (dp[n][roll][jump] != -1) return dp[n][roll][jump]; // Recursive Calls: // If the person chooses to walk int w = solver(n - 1, roll, 0); // If the person chooses to roll int r = solver(n - 1, roll + 1, 0); // If the person chooses to jump int j = solver(n - 1, roll, jump + 1); // Calculate total valid sequences, and store // in dp for later use return dp[n][roll][jump] = ((w + r) % mod + j) % mod;}// Function to initialize memoization array// and start solvingint checkDistance(int n){ // Initialize dp array with -1 memset(dp, -1, sizeof(dp)); // Start solving with initial parameters return solver(n, 0, 0);}// Main Functionint main(){ // Print the result of checkDistance(7) cout << checkDistance(6); return 0;} |
200
Time Complexity: O(n), where ‘n’ is the total distance to be travelled.
Auxiliary Space: O(n*2*3) = O(n).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
