Problem

Submissions

Hints & solutions

Discuss

Count Number Of Ways To Cover A Distance

Easy

0/40

Average time to solve is 15m

Contributed by

7 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
3 
4

Sample Output 1:

4
7

Explanation of the Sample Input 1:

Test case 1:

Below are the four ways
1 step + 1 step + 1 step
1 step + 2 step
2 step + 1 step
3 step

Test case 2:

Below are the seven ways
1 step + 1 step + 1 step + 1 step
1 step + 2 step + 1 step
2 step + 1 step + 1 step 
1 step + 1 step + 2 step
2 step + 2 step
3 step + 1 step
1 step + 3 step

Sample Input 2:

2
1
2

Sample Output 2:

1
2

Explanation of the Sample Input 2:

Test case 1:
Below is the only way
1 step

Test case 2:
Below are the three ways
1step + 1 step
2 step

Hint 1

Hint 2

Hint 3

Hint 4

Use backtracking.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Recursive Force

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.

Time Complexity

O(3^N), where ‘N’ is the distance.

The time complexity of the above solution is exponential, a close upper bound is O(3^N). From each state, a recursive function is called. So the upper bound for ‘N’ states is O(3^N).

Space Complexity

O(N), where ‘N’ is the distance.

As the recursive function is based on the stack it will go up to taking size ‘N’ in the stack.

(100% EXP penalty)

Count Number Of Ways To Cover A Distance

Console