Railway Station | TCS CodeVita 2020

Namachila October 13, 2025

0 0 9 minutes read

Given an integer N, representing the number of stations lying between the source and the destination. There are three trains available from every station and their stoppage patterns are as follows:

Train 1: Stops at every station
Train 2: Stops at every alternate station
Train 3: Stops at every third station

The task is to find the number of ways to reach the destination from the source using any possible combination of trains.

Examples:

Input: N = 2
Output: 4
Explanation:
Four possible ways exists to travel from source to destination with 2 stations in between:
Train 1 (from source) -> Train 1 (from station 1) -> Train 1(from station 2) -> Destination
Train 2 (from source) -> Train 1 (from station 2) -> Destination
Train 1 (from source) -> Train 2 (from station 1) -> Destination
Train 3 (from source) -> Destination

Input: N = 0
Output: 1
Explanation: No station is present in between the source and destination. Therefore, there is only one way to travel, i.e.
Train 1(from source) -> Destination

Approach: The main idea to solve the problem is to use Recursion with Memoization to solve this problem. The recurrence relation is as follows:

F(N) = F(N – 1) + F(N – 2) + F(N – 3),

where,
F(N – 1) counts ways to travel upto (N – 1)^th station.
F(N – 2) counts ways to travel upto (N – 2)^th station.
F(N – 3) counts ways to travel upto (N – 3)^th station.

Follow the steps below to solve the problem:

Initialize an array dp[] for memorization. Set all indices to -1 initially.
Define a recursive function findWays() to calculate the number of ways to reach the N^th station.
Following base cases are required to be considered:
- For x < 0 return 0.
- For x = 0, return 1.
- For x = 1, return 2.
- For x = 2, return 4.
If the current state, say x, is already evaluated i.e. dp[x] is not equal to -1, simply return the evaluated value.
Otherwise, calculate findWays(x – 1), findWays(x – 2) and findWays(x – 3) recursively and store their sum in dp[x].
Return dp[x].

Below is the implementation of the above approach:

C++14

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Dp table for memoization
int dp[100000];
 
// Function to count the number
// of ways to N-th station
int findWays(int x)
{
    // Base Cases
    if (x < 0)
        return 0;
 
    if (x == 0)
        return 1;
 
    if (x == 1)
        return 2;
 
    if (x == 2)
        return 4;
 
    // If current state is
    // already evaluated
    if (dp[x] != -1)
        return dp[x];
 
    // Recursive calls
 
    // Count ways in which
    // train 1 can be chosen
    int count = findWays(x - 1);
 
    // Count ways in which
    // train 2 can be chosen
    count += findWays(x - 2);
 
    // Count ways in which
    // train 3 can be chosen
    count += findWays(x - 3);
 
    // Store the current state
    dp[x] = count;
 
    // Return the number of ways
    return dp[x];
}
 
// Driver Code
int main()
{
 
    // Given Input
    int n = 4;
 
    // Initialize DP table with -1
    memset(dp, -1, sizeof(dp));
 
    // Function call to count
    // the number of ways to
    // reach the n-th station
    cout << findWays(n) << "\n";
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Dp table for memoization
  static int dp[] = new int[100000];
 
  // Function to count the number
  // of ways to N-th station
  static int findWays(int x)
  {
 
    // Base Cases
    if (x < 0)
      return 0;
 
    if (x == 0)
      return 1;
 
    if (x == 1)
      return 2;
 
    if (x == 2)
      return 4;
 
    // If current state is
    // already evaluated
    if (dp[x] != -1)
      return dp[x];
 
    // Recursive calls
 
    // Count ways in which
    // train 1 can be chosen
    int count = findWays(x - 1);
 
    // Count ways in which
    // train 2 can be chosen
    count += findWays(x - 2);
 
    // Count ways in which
    // train 3 can be chosen
    count += findWays(x - 3);
 
    // Store the current state
    dp[x] = count;
 
    // Return the number of ways
    return dp[x];
  }
 
  // Driven Code
  public static void main(String[] args)
  {
 
    // Given Input
    int n = 4;
 
    // Initialize DP table with -1
    Arrays.fill(dp, -1);
 
    // Function call to count
    // the number of ways to
    // reach the n-th station
    System.out.print(findWays(n));
  }
}
 
// This code is contributed by splevel62.

Python3

# Python3 program of the above approach
 
# Dp table for memoization
dp = [-1 for i in range(100000)]
 
# Function to count the number
# of ways to N-th station
def findWays(x):
     
    # Base Cases
    if (x < 0):
        return 0
 
    if (x == 0):
        return 1
 
    if (x == 1):
        return 2
 
    if (x == 2):
        return 4
 
    # If current state is
    # already evaluated
    if (dp[x] != -1):
        return dp[x]
 
    # Recursive calls
 
    # Count ways in which
    # train 1 can be chosen
    count = findWays(x - 1)
 
    # Count ways in which
    # train 2 can be chosen
    count += findWays(x - 2)
 
    # Count ways in which
    # train 3 can be chosen
    count += findWays(x - 3)
 
    # Store the current state
    dp[x] = count
 
    # Return the number of ways
    return dp[x]
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    n = 4
     
    # Function call to count
    # the number of ways to
    # reach the n-th station
    print(findWays(n))
 
# This code is contributed by SURENDRA_GANGWAR

C#

// C# program to implement above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // Dp table for memoization
  static int[] dp = new int[100000];
 
  // Function to count the number
  // of ways to N-th station
  static int findWays(int x)
  {
    // Base Cases
    if (x < 0)
      return 0;
 
    if (x == 0)
      return 1;
 
    if (x == 1)
      return 2;
 
    if (x == 2)
      return 4;
 
    // If current state is
    // already evaluated
    if (dp[x] != -1)
      return dp[x];
 
    // Recursive calls
 
    // Count ways in which
    // train 1 can be chosen
    int count = findWays(x - 1);
 
    // Count ways in which
    // train 2 can be chosen
    count += findWays(x - 2);
 
    // Count ways in which
    // train 3 can be chosen
    count += findWays(x - 3);
 
    // Store the current state
    dp[x] = count;
 
    // Return the number of ways
    return dp[x];
  }
 
  // Driver Code
  public static void Main(string[] args){
 
    // Given Input
    int n = 4;
 
    // Initialize DP table with -1
    for(int i = 0 ; i < dp.Length ; i++){
      dp[i] = -1;
    }
 
    // Function call to count
    // the number of ways to
    // reach the n-th station
    Console.Write(findWays(n) + "\n");
 
  }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

<script>
 
// JavaScript program of the above approach
 
// Dp table for memoization
let dp = new Array(100000).fill(-1)
 
// Function to count the number
// of ways to N-th station
function findWays(x){
     
    // Base Cases
    if (x < 0)
        return 0
 
    if (x == 0)
        return 1
 
    if (x == 1)
        return 2
 
    if (x == 2)
        return 4
 
    // If current state is
    // already evaluated
    if (dp[x] != -1)
        return dp[x]
 
    // Recursive calls
 
    // Count ways in which
    // train 1 can be chosen
    let count = findWays(x - 1)
 
    // Count ways in which
    // train 2 can be chosen
    count += findWays(x - 2)
 
    // Count ways in which
    // train 3 can be chosen
    count += findWays(x - 3)
 
    // Store the current state
    dp[x] = count
 
    // Return the number of ways
    return dp[x]
}
 
// Driver Code
     
// Given Input
let n = 4
 
// Function call to count
// the number of ways to
// reach the n-th station
document.write(findWays(n))
 
// This code is contributed by shinjanpatra
 
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Efficient approach : Using DP Tabulation method ( Iterative approach )

The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.

Steps to solve this problem :

Take the integer N as input.
Initialize a DP table of size N+1 to store the number of ways to reach each station.
Base cases: set the initial values of the DP table for the first three stations.
Traverse the stations from 3 to N and for each station:
a. Calculate the number of ways to reach the current station by considering the number of ways to reach the two previous stations.
b. Update the DP table with the new number of ways to reach the current station.
Return the number of ways to reach the N-th station from the DP table.

Implementation :

C++

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number
// of ways to N-th station
int findWays(int x)
{
    // initialize Dp
    vector<int> dp(x + 1, 0);
 
    // Base Cases
    dp[0] = 1;
    dp[1] = 2;
    dp[2] = 4;
 
    // initialize count
    // Count ways in which
    // train 1 can be chosen
    int count = dp[2];
 
    for (int i = 3; i <= x; i++) {
        // Count ways in which
        // train 2 can be chosen
        count += dp[i - 2];
        // Count ways in which
        // train 3 can be chosen
        count += dp[i - 3];
        // Store the current state
        dp[i] = count;
    }
 
    // Return the number of ways
    return dp[x];
}
 
// Driver Code
int main()
{
 
    // Given Input
    int n = 2;
 
    // Function call to count
    // the number of ways to
    // reach the n-th station
    cout << findWays(n) << "\n";
}
// this code is contributed by bhardwajji

Java

// Java program of the above approach
import java.util.*;
 
public class Main
{
   
// Function to count the number
// of ways to N-th station
public static int findWays(int x) 
{
   
// initialize Dp
int[] dp = new int[x + 1];
      // Base Cases
    dp[0] = 1;
    dp[1] = 2;
    dp[2] = 4;
 
    // initialize count
    // Count ways in which
    // train 1 can be chosen
    int count = dp[2];
 
    for (int i = 3; i <= x; i++)
    {
       
        // Count ways in which
        // train 2 can be chosen
        count += dp[i - 2];
       
        // Count ways in which
        // train 3 can be chosen
        count += dp[i - 3];
       
        // Store the current state
        dp[i] = count;
    }
 
    // Return the number of ways
    return dp[x];
}
 
// Driver Code
public static void main(String[] args) 
{
   
    // Given Input
    int n = 2;
 
    // Function call to count
    // the number of ways to
    // reach the n-th station
    System.out.println(findWays(n));
}
}

Python3

# Function to count the number
# of ways to N-th station
def findWays(x):
    # initialize Dp
    dp = [0] * (x + 1)
 
    # Base Cases
    dp[0] = 1
    dp[1] = 2
    dp[2] = 4
 
    # initialize count
    # Count ways in which
    # train 1 can be chosen
    count = dp[2]
 
    for i in range(3, x + 1):
        # Count ways in which
        # train 2 can be chosen
        count += dp[i - 2]
        # Count ways in which
        # train 3 can be chosen
        count += dp[i - 3]
        # Store the current state
        dp[i] = count
 
    # Return the number of ways
    return dp[x]
 
# Driver Code
if __name__ == '__main__':
    # Given Input
    n = 2
 
    # Function call to count
    # the number of ways to
    # reach the n-th station
    print(findWays(n))

C#

using System;
 
class Solution 
{
 
  // Function to count the number
  // of ways to N-th station
  public int findWays(int x)
  {
 
    // initialize Dp
    int[] dp = new int[x + 1];
 
    // Base Cases
    dp[0] = 1;
    dp[1] = 2;
    dp[2] = 4;
 
    // initialize count
    // Count ways in which
    // train 1 can be chosen
    int count = dp[2];
 
    for (int i = 3; i <= x; i++)
    {
 
      // Count ways in which
      // train 2 can be chosen
      count += dp[i - 2];
 
      // Count ways in which
      // train 3 can be chosen
      count += dp[i - 3];
 
      // Store the current state
      dp[i] = count;
      count = 0;
    }
 
    // Return the number of ways
    return dp[x];
  }
}
 
// Driver Code
public class Program {
  static void Main(string[] args)
  {
    Solution obj = new Solution();
 
    // Given Input
    int n = 2;
 
    // Function call to count
    // the number of ways to
    // reach the n-th station
    Console.WriteLine(obj.findWays(n));
  }
}
 
// This code is contributed by usr_dtewbxkn77n

Javascript

// JavaScript program of the above approach
function findWays(x) {
    // initialize Dp
    let dp = new Array(x + 1).fill(0);
 
    // Base Cases
    dp[0] = 1;
    dp[1] = 2;
    dp[2] = 4;
 
    // initialize count
    // Count ways in which
    // train 1 can be chosen
    let count = dp[2];
 
    for (let i = 3; i <= x; i++) 
    {
     
        // Count ways in which
        // train 2 can be chosen
        count += dp[i - 2];
         
        // Count ways in which
        // train 3 can be chosen
        count += dp[i - 3];
         
        // Store the current state
        dp[i] = count;
    }
 
    // Return the number of ways
    return dp[x];
}
 
// Driver Code
let n = 2;
 
// Function call to count
// the number of ways to
// reach the n-th station
console.log(findWays(n));
 
// This code is contributed by sarojmcy2e

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!