Baseline Graphs · Learning O(1) · O(1)
A network architect is asked how many distinct wiring plans exist for a closed lab of n machines, where every unordered machine pair may either have a cable or not — nothing else distinguishes one plan from another. Every pair contributes an independent yes/no choice, so the plans multiply out to a simple power of two.
Input: An integer n — the number of vertices.
Output: Return 2 raised to the number of possible undirected edges, i.e. 2^(n*(n-1)/2).
1 <= n <= 20Input: {"n":1}
Output: 1
A lone vertex has no possible edges, so only the empty graph exists.
Input: {"n":3}
Output: 8
Three vertex pairs means 2^3 = 8 wiring plans.