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.
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.
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.
Can you solve this using only O(1) space?
1 <= T <= 50
1 <= N <= 10^4
Time Limit: 1 sec
2
3
4
4
7
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
2
1
2
1
2
Test case 1:
Below is the only way
1 step
Test case 2:
Below are the three ways
1step + 1 step
2 step
Use backtracking.
Approach:
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).
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.
All tags
Sort by
Interview problems
C++ DP Memoization
#include <bits/stdc++.h>
long long mod = 1e9 + 7;
int fun(int n, vector<int> &dp) {
if(n==0) return 1;
if(dp[n]!=-1) return dp[n];
long long os = 0, ts = 0, ths = 0;
if(n>=1) os = fun(n-1, dp);
if(n>=2) ts = fun(n-2, dp);
if(n>=3) ths = fun(n-3, dp);
return dp[n] = (int)((os + ts + ths)%mod);
}
int distance(int n) {
// Write your code here
vector<int> dp(n+1,-1);
return fun(n, dp);
}
Interview problems
Python using Memoization
from os import *
from sys import *
from collections import *
from math import *
def count(sum,n,ans,dp):
if sum==n:
return 1
if sum>n:
return 0
if dp[sum]!=-1:
return dp[sum]
a=count(sum+1,n,ans,dp)
b=count(sum+2,n,ans,dp)
c=count(sum+3,n,ans,dp)
dp[sum]=a+b+c
return dp[sum]
def distance(n) :
if n==0:
return 0
dp=[-1 for i in range(n+1)]
return count(0,n,[0],dp)%(10**9+7)Interview problems
MEMOIZATION | C++
#include <bits/stdc++.h>
#define MOD 1000000007
#define lli long long int
lli f(int n, vector<lli>& dp){
if(n==0) return 1;
if(n<0) return 0;
if(dp[n]!=-1) return dp[n];
return dp[n]=(f(n-1, dp) + f(n-2, dp) +f(n-3, dp))%MOD;
}
int distance(int n) {
vector<lli> dp(n+1, -1);
return f(n, dp);
}
Interview problems
memoization || tabulation || space optimized
#include <bits/stdc++.h>
int mod= 1e9+7;
//recursion + memoization
int f(int n,vector<int> &dp)
{
if(n<0)
return 0;
if(n==0)
return dp[0]=1;
if(dp[n]!=-1) return dp[n];
int one= f(n-1,dp)%mod;
int two= f(n-2,dp)%mod;
int three= f(n-3,dp)%mod;
return dp[n]=(((one+three)%mod)+two)%mod;
}
int distanc(int n) {
//tabulation
vector<int> dp(n+1,-1);
dp[0]=1;
for(int i=1; i<=n; i++)
{
int o=0,t=0,th=0;
if(i>0)
o= dp[i-1]%mod;
if(i>1)
t= dp[i-2]%mod;
if(i>2)
th= dp[i-3]%mod;
dp[i]=(((o+t)%mod)+th)%mod;
}
return dp[n];
// return f(n,dp);
}
int distance(int n)
{
//tabulation(space optimized)
int x=0,y=0,z=0,cur;
z=1;
for(int i=1; i<=n; i++)
{
int o=0,t=0,th=0;
if(i>0)
o= z%mod;
if(i>1)
t= y%mod;
if(i>2)
th= x%mod;
cur=(((o+t)%mod)+th)%mod;
x=y;y=z;z=cur;
}
return cur;
}Interview problems
Short and Simple solution
// short and simole solution
#include <bits/stdc++.h>
int f(int n,int i,vector<vector<int>> &dp){
if(n==0) return 1;
if(i>n || i>3) return 0;
if(dp[n][i]!=-1) return dp[n][i];
int l = f(n-i,1,dp);
int r = f(n,i+1,dp);
return dp[n][i]=l+r;
}
int distance(int n) {
// Write your code here
vector<vector<int>> dp(n+1,vector<int>(4,-1));
return f(n,1,dp);
}Interview problems
Discussion thread on Interview Problem | Count Number Of Ways To Cover A Distance
Hey everyone, creating this thread to discuss the interview problem - Count Number Of Ways To Cover A Distance.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Count Number Of Ways To Cover A Distance
