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 = 3
Output: 6
Explanation: 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?1Input: N = 5, K = 3
Output: 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 store the number of ways to reach all the nodes.
- 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].
- 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 edgesvoid 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 Codeint main(){ // Given Input int N = 5, K = 3; // Function Call numberOfWays(N, K); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find number of ways to// reach from node 1 to 1 again, after// moving exactly K edgesstatic 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 Codepublic 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 edgesdef 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 Codeif __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 approachusing System;class GFG{// Function to find number of ways to// reach from node 1 to 1 again, after// moving exactly K edgesstatic 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 Codestatic 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 edgesfunction 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 Inputlet N = 5;let K = 3;// Function CallnumberOfWays(N, K);</script> |
Output
12
Time Complexity: O(N×K)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
