Last Updated: 18 Dec, 2020
Count Number Of Ways To Cover A Distance
Easy
Asked in companies
Divyansh is in Dhanbad and wants to travel to different places. He can take one, two or three steps at max while travelling. He knows the distance and wants to find the number of ways to reach his destination. He is weak at calculations and wants your help in this. Given the distance from Dhanbad to his destination, count the total number of ways to cover the distance with 1, 2 and 3 steps.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
The first and the only line of each test case contains an integer ‘N’ denoting the distance between Dhanbad and the destination.
Output Format:-
For each test case, print an integer denoting the number of ways to cover the distance.
Print the answer mod 10^9+7.
Note :
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Follow Up:
Can you solve this using only O(1) space?
Constraints:
1 <= T <= 50
1 <= N <= 10^4
Time Limit: 1 sec
Approaches
Approach:
- Create a recursive function that takes only one parameter.
- Check the base cases. If the value of ‘N’ is less than 0 then return 0, and if the value of N is equal to zero then return 1 as it is the starting position.
- Call the function recursively with values ‘N-1’, ‘N-2’, and ‘N-3’ and sum up the values that are returned.
- Return the value of the sum.
Approach:
- As we can see in the recursive approach that every time some distance “i” is asked it calculates the number of ways. Rather than that if we store the answer for every “i” it will help.
Algorithm:
- Create a recursive function that takes only one parameter. Make a global array DP and initialize it with 0 and Dp[0] =1(Base case).
- Check the base cases. If the value of ‘N’ is less than 0 then return 0, and if the value of ‘N’ is equal to zero then return 1 as it is the starting position.
- If DP of i is not 0 we return the value else we call the function recursively with values ‘N-1’, ‘N-2’, and 'N-3’ and sum up the values that are returned. Also, we store the value of the number of ways for that distance in our DP array.
- Return the value of the sum.
Approach:
- Every distance ‘D’ can be reached from three back steps. So, if we know the number of ways to reach ‘D-1’, 'D-2', 'D-3'. Then we can take their sum and that will be our answer.
Algorithm:
- Create an array of size ‘N + 1’ and initialize the first 3 variables with 1, 1, 2.
- Run a loop from 3 to N.
- For each index i, computer value of ‘ith’ position as dp[i] = dp[i-1] + dp[i-2] + dp[i-3].
- Return the value of dp[N], as the Count of number of ways to cover a distance.
Approach:
- Every distance ‘D’ can be reached from three back steps. So, if we know the number of ways to reach ‘D-1’, ‘D-2’, ‘D-3’. Then we can take their sum and that will be our answer. We can see we are only using last 4 values of the array at max so we can use modulus concept here.
Algorithm:
- Create an array of size 4 and initialize the first 3 variables with 1, 1, 2.
- Run a loop from 3 to ‘N’.
- For each index i, computer value of ‘ith’ position as dp[(i)%4] = dp[(i-1)%4] + dp[(i-2)%4] + dp[(i-3)%4].
- Return the value of dp[N%4], as the Count of the number of ways to cover a distance.
Similar problems