Sample cases
Case 1: n = 3, k = 3
Output: 2
Case 2: n = 4, k = 2
Output: 3
Case 3: n = 4, k = 3
Output: 6
Case 4: n = 5, k = 2
Output: 4
Solution
Let f(n, k) be a function to generate the number of ways of traversing the graph by visiting k nodes. As we start from one node and return to it, we visit k-1 nodes, excluding the starting node. Since we exclude the starting node, we have n-1 choices to select the intermediate nodes. So for every intermediate node, there are n-1 options. This suggests that there are n-1k-1 ways. To avoid repeating the edges after every traversal, we subtract f(n, k-1). So the final recursive equation is as follows:
The base case for this equation is f(n, 2) = n - 1. This can be proved by observing cases 2 and 4. Irrespective of the value of n, if k is 2, then the number of ways of traversing is always n-1. Upon expanding the recursive equation, we obtain the following.
Let the above equation be Eq1. Dividing Eq1 by (n-1) gives the following.
Let this be Eq2. Adding Eq1 and Eq2 results in the following equation.
Solving this further, we obtain the following.
Code
Now, let us implement the solution as code in Python, Java and C++.
Python Code
def solution(n,k):
x = n-1
# if k&1 returns 1, k is odd, else even
if (k & 1):
return (pow(x, k) - x) / n
return (pow(x, k) + x) / n
# n,k = map(int,input().split())
n = k = 3
print (int(solution(n, k)))
You can also try this code with Online Python Compiler
Run Code
Java Code
import java.io.*;
public class Main
{
static int solution(int n,int k)
{
int x = n-1;
// if k&1 returns 1, k is odd, else even
if ((k & 1) == 1)
return (int)(Math.pow(x, k) -x) / n;
return (int)(Math.pow(x, k) + x) / n;
}
public static void main(String args[])
{
int n = 3, k = 3;
System.out.println(solution(n, k));
}
}
You can also try this code with Online Java Compiler
Run Code
C++ Code
#include <bits/stdc++.h>
using namespace std;
int solution(int n, int k)
{
int x = n-1;
// if k&1 returns 1, k is odd, else even
if ((k & 1) == 1)
return (pow(x, k) - x) / n;
return (pow(x, k) + x) / n;
}
int main()
{
int n = 3, k = 3;
cout << solution(n, k) << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
Output:
2
Complexity
Time and space complexity is O(1).
Check out this problem - Shortest Common Supersequence.
Frequently Asked Questions
What are graph traversal algorithms?
Breadth-first search and depth-first search are two graph traversal algorithms. In breadth-first search, all adjacent nodes of a single node are visited. In depth-first search, after the adjacent vertices for a starting vertex are found, it moves to that vertex and tries to traverse it similarly.
What is a path and cycle in graphs?
A path defines a sequence of vertices connected by edges. A cycle is a path having the same starting and ending point.
Name a method to detect cycles in an undirected graph.
We can use BFS, DFS and union-find algorithms to detect cycles in an undirected graph. In the BFS method, for every visited vertex ‘v’, if there is an adjacent vertex ‘u’ such that u is already visited and u is not a parent of v, there is a cycle in the graph. If there is no such adjacent for any vertex, there is no cycle.
Conclusion
This blog discusses how to find the number of loops of size k starting from a specific node in a completely connected undirected graph. Check out our articles on Detecting cycles in a directed graph, detecting cycles in an undirected graph and properties of graphs. Explore our Library on Coding Ninjas Studio to gain knowledge on Data Structures and Algorithms, Machine Learning, Deep Learning, Cloud Computing and many more! Test your coding skills by solving our test series and participating in the contests hosted on Coding Ninjas Studio!
Looking for questions from tech giants like Amazon, Microsoft, Uber, etc.? Look at the problems, interview experiences, and interview bundle for placement preparations. Upvote our blogs if you find them insightful and engaging! Happy Coding!