# Number of ways to reach at starting node after travelling through exactly K edges in a complete graph

Given a complete graph having **N **nodes and **N*(N-1)/2** edges and a positive integer **K**, the task is to find the number of ways if you are starting at node **1** and end at the same node if exactly **K **edges have to be traversed.

Input:N = 4, K = 3Output:6Explanation:The possible ways are-

1→2→3→1

1→2→4→1

1→3→2→1

1→3→4→1

1→4→2→1

1→4→3→1Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

Input:N = 5, K = 3Output:12

**Naive Approach: **The simplest approach to solve this problem is to traverse from every edge from the current vertex it will lead the solution to be exponential time.

**Time Complexity: **O(N^N)* Auxiliary Space: O(N), due to stack space in *the

*recursive function*

*call.*

**Efficient Approach: **This problem has Overlapping Subproblems property and Optimal Substructure property. So this problem can be solved using Dynamic Programming. Like other typical Dynamic Programming(DP) problems, recomputation of the same subproblems can be avoided by constructing a temporary array that stores results of subproblems. Follow the steps below to solve the problem:

- Initialize a
**dp[]**array where**dp[i]**to stores the number of ways to reach at**ith**node and initialize**dp[0]**as**1.** - Iterate in the range
**[1, K]**using the variable**i**and perform the following steps:- Initialize a variable
**numWays**as**0**to - Iterate in the range
**[0, N-1]**using the variable**j,**then add**dp[j]**in**numWays.** - Iterate in the range
**[0, N-1]**using the variable**j,**then update the value of**dp[j]**as maximum of**dp[j]**and**numWays – dp[j]**.

- Initialize a variable
- After performing the above steps, print
**dp[0]**as the answer.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find number of ways to` `// reach from node 1 to 1 again, after` `// moving exactly K edges` `void` `numberOfWays(` `int` `n, ` `int` `k)` `{` ` ` `// Initialize a dp[] array, where dp[i]` ` ` `// stores number of ways to reach at` ` ` `// a i node` ` ` `int` `dp[1000];` ` ` `// Initialize the dp array with 0` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `dp[i] = 0;` ` ` `}` ` ` `// Base Case` ` ` `dp[0] = 1;` ` ` `// Iterate for the number of edges moved` ` ` `for` `(` `int` `i = 1; i <= k; i++) {` ` ` `// Sum will store number of ways to` ` ` `// reach all the nodes` ` ` `int` `numWays = 0;` ` ` `// Iterate for every possible state` ` ` `// for the current step` ` ` `for` `(` `int` `j = 0; j < n; j++) {` ` ` `numWays += dp[j];` ` ` `}` ` ` `// Update the value of the dp array` ` ` `// after travelling each edge` ` ` `for` `(` `int` `j = 0; j < n; j++) {` ` ` `dp[j] = numWays - dp[j];` ` ` `}` ` ` `}` ` ` `// Print dp[0] as the answer` ` ` `cout << dp[0] << endl;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given Input` ` ` `int` `N = 5, K = 3;` ` ` `// Function Call` ` ` `numberOfWays(N, K);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `class` `GFG{` `// Function to find number of ways to` `// reach from node 1 to 1 again, after` `// moving exactly K edges` `static` `void` `numberOfWays(` `int` `n, ` `int` `k) ` `{` ` ` ` ` `// Initialize a dp[] array, where dp[i]` ` ` `// stores number of ways to reach at` ` ` `// a i node` ` ` `int` `[] dp = ` `new` `int` `[` `1000` `];` ` ` `// Initialize the dp array with 0` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++)` ` ` `{` ` ` `dp[i] = ` `0` `;` ` ` `}` ` ` `// Base Case` ` ` `dp[` `0` `] = ` `1` `;` ` ` `// Iterate for the number of edges moved` ` ` `for` `(` `int` `i = ` `1` `; i <= k; i++) ` ` ` `{` ` ` ` ` `// Sum will store number of ways to` ` ` `// reach all the nodes` ` ` `int` `numWays = ` `0` `;` ` ` `// Iterate for every possible state` ` ` `// for the current step` ` ` `for` `(` `int` `j = ` `0` `; j < n; j++)` ` ` `{` ` ` `numWays += dp[j];` ` ` `}` ` ` `// Update the value of the dp array` ` ` `// after travelling each edge` ` ` `for` `(` `int` `j = ` `0` `; j < n; j++) ` ` ` `{` ` ` `dp[j] = numWays - dp[j];` ` ` `}` ` ` `}` ` ` `// Print dp[0] as the answer` ` ` `System.out.println(dp[` `0` `] + ` `"\n"` `);` `}` `// Driver Code` `public` `static` `void` `main(String args[]) ` `{` ` ` ` ` `// Given Input` ` ` `int` `N = ` `5` `, K = ` `3` `;` ` ` `// Function Call` ` ` `numberOfWays(N, K);` `}` `}` `// This code is contributed by _saurabh_jaiswal` |

## Python3

`# Python 3 program for the above approach` `# Function to find number of ways to` `# reach from node 1 to 1 again, after` `# moving exactly K edges` `def` `numberOfWays(n, k):` ` ` ` ` `# Initialize a dp[] array, where dp[i]` ` ` `# stores number of ways to reach at` ` ` `# a i node` ` ` `dp ` `=` `[` `0` `for` `i ` `in` `range` `(` `1000` `)]` ` ` `# Base Case` ` ` `dp[` `0` `] ` `=` `1` ` ` `# Iterate for the number of edges moved` ` ` `for` `i ` `in` `range` `(` `1` `, k ` `+` `1` `, ` `1` `):` ` ` ` ` `# Sum will store number of ways to` ` ` `# reach all the nodes` ` ` `numWays ` `=` `0` ` ` `# Iterate for every possible state` ` ` `# for the current step` ` ` `for` `j ` `in` `range` `(n):` ` ` `numWays ` `+` `=` `dp[j]` ` ` `# Update the value of the dp array` ` ` `# after travelling each edge` ` ` `for` `j ` `in` `range` `(n):` ` ` `dp[j] ` `=` `numWays ` `-` `dp[j]` ` ` `# Print dp[0] as the answer` ` ` `print` `(dp[` `0` `])` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `# Given Input` ` ` `N ` `=` `5` ` ` `K ` `=` `3` ` ` `# Function Call` ` ` `numberOfWays(N, K)` ` ` ` ` `# This code is contributed by SURENDRA_GANGWAR.` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `// Function to find number of ways to` `// reach from node 1 to 1 again, after` `// moving exactly K edges` `static` `void` `numberOfWays(` `int` `n, ` `int` `k)` `{` ` ` ` ` `// Initialize a dp[] array, where dp[i]` ` ` `// stores number of ways to reach at` ` ` `// a i node` ` ` `int` `[] dp = ` `new` `int` `[1000];` ` ` `// Initialize the dp array with 0` ` ` `for` `(` `int` `i = 0; i < n; i++) ` ` ` `{` ` ` `dp[i] = 0;` ` ` `}` ` ` `// Base Case` ` ` `dp[0] = 1;` ` ` `// Iterate for the number of edges moved` ` ` `for` `(` `int` `i = 1; i <= k; i++) ` ` ` `{` ` ` ` ` `// Sum will store number of ways to` ` ` `// reach all the nodes` ` ` `int` `numWays = 0;` ` ` `// Iterate for every possible state` ` ` `// for the current step` ` ` `for` `(` `int` `j = 0; j < n; j++)` ` ` `{` ` ` `numWays += dp[j];` ` ` `}` ` ` `// Update the value of the dp array` ` ` `// after travelling each edge` ` ` `for` `(` `int` `j = 0; j < n; j++)` ` ` `{` ` ` `dp[j] = numWays - dp[j];` ` ` `}` ` ` `}` ` ` `// Print dp[0] as the answer` ` ` `Console.Write(dp[0]);` `}` `// Driver Code` `static` `public` `void` `Main ()` `{` ` ` ` ` `// Given Input` ` ` `int` `N = 5, K = 3;` ` ` `// Function Call` ` ` `numberOfWays(N, K);` `}` `}` `// This code is contributed by sanjoy_62` |

## Javascript

`<script>` `// JavaScript program for the above approach` `// Function to find number of ways to` `// reach from node 1 to 1 again, after` `// moving exactly K edges` `function` `numberOfWays(n, k)` `{` ` ` ` ` `// Initialize a dp[] array, where dp[i]` ` ` `// stores number of ways to reach at` ` ` `// a i node` ` ` `let dp = Array(1000);` ` ` `// Initialize the dp array with 0` ` ` `for` `(let i = 0; i < n; i++) ` ` ` `{` ` ` `dp[i] = 0;` ` ` `}` ` ` `// Base Case` ` ` `dp[0] = 1;` ` ` `// Iterate for the number of edges moved` ` ` `for` `(let i = 1; i <= k; i++) ` ` ` `{` ` ` ` ` `// Sum will store number of ways to` ` ` `// reach all the nodes` ` ` `let numWays = 0;` ` ` `// Iterate for every possible state` ` ` `// for the current step` ` ` `for` `(let j = 0; j < n; j++)` ` ` `{` ` ` `numWays += dp[j];` ` ` `}` ` ` `// Update the value of the dp array` ` ` `// after travelling each edge` ` ` `for` `(let j = 0; j < n; j++)` ` ` `{` ` ` `dp[j] = numWays - dp[j];` ` ` `}` ` ` `}` ` ` `// Print dp[0] as the answer` ` ` `document.write(dp[0]);` `}` `// Driver Code` `// Given Input` `let N = 5;` `let K = 3;` `// Function Call` `numberOfWays(N, K);` `</script>` |

**Output**

12

**Time Complexity: **O(N×K)**Auxiliary Space: **O(N)