Problem

Given two positive integers n and k, consider a complete undirected graph with n nodes. Find the number of distinct cycles (loops) of length k that start and end at a specific node, visiting exactly k nodes (nodes may not repeat except for the start/end).

Examples

Example 1

1
2
3
4
5
6

Input:
n = 3, k = 3
Output: 2
Explanation: See the graphs below for 2 paths:
- 1 -> 2 -> 3 -> 1
- 1 -> 3 -> 2 -> 1

graph LR;
	A(1) --- B(2) --- C(3) --- A
	D(1) --- F(3) --- E(2) --- D

Example 2

1
2
3

Input:
n = 4, k = 2
Output: 3

Solution

Method 1 – Combinatorial Recurrence

Intuition

In a complete graph, every node is directly connected to every other node. To count the number of cycles (loops) of length $k$ that start and end at a specific node, we need to consider all possible ways to visit $k-1$ other nodes (since the start/end node is fixed), making sure that:

  • Each node in the cycle (except the start/end) is visited exactly once (no repeats).
  • The path returns to the starting node after $k$ steps.

At first glance, it might seem like we can simply count all possible sequences of $k-1$ nodes chosen from the remaining $n-1$ nodes, but this would overcount cycles that revisit nodes or form smaller loops within the $k$ steps. We need a way to count only the valid cycles of length exactly $k$.

Approach

Let $f(n, k)$ be the number of cycles of length $k$ that start and end at a specific node in a complete graph with $n$ nodes.

  1. First Step:
  • We start at a fixed node. For the first move, we can go to any of the $n-1$ other nodes.
  1. Subsequent Steps:
  • For each of the next $k-2$ steps, we must move to a new node that we haven’t visited yet (to avoid revisiting nodes and forming smaller cycles). For each step, there are fewer choices, but in a complete graph, the number of ways to choose a sequence of $k-1$ distinct nodes is $(n-1) \times (n-2) \times \ldots \times (n-k+1)$.
  1. Returning to Start:
  • After $k-1$ moves, we must return to the starting node to complete the cycle.
  1. Avoiding Overcounting:
  • However, this approach still overcounts cycles that contain smaller loops (i.e., cycles of length less than $k$ that are traversed multiple times). To correct for this, we use a recurrence relation that subtracts the number of cycles of smaller length already counted.

The recurrence relation is:

$$ f(n, k) = (n-1)^{k-1} - f(n, k-1) $$

with the base case:

$$ f(n, 2) = n-1 $$

This recurrence can be solved to obtain a closed formula:

$$ f(n,k) = \frac{(n-1)^k + (-1)^k(n - 1)}{n} $$

Code

1
2
3
4
5
6
7

class Solution {
public:
  int countCycles(int n, int k) {
    int p = (k % 2 == 0) ? 1 : -1;
    return (pow(n-1, k) + p * (n-1)) / n;
  }
};
1
2
3
4
5
6

class Solution {
  public int countCycles(int n, int k) {
    int p = (k % 2 == 0) ? 1 : -1;
    return (int)((Math.pow(n-1, k) + p * (n-1)) / n);
  }
}
1
2
3
4

class Solution:
  def count_cycles(self, n: int, k: int) -> int:
    p = 1 if k % 2 == 0 else -1
    return ((n-1)**k + p * (n-1)) // n

Complexity

  • ⏰ Time complexity: O(1), as the formula is direct and does not require iteration.
  • 🧺 Space complexity: O(1), only a few variables are used.