Intergalactic Travel Planner — Problem Statement & Solution Guide
Problem Description
Given a positive integer n representing the number of wormholes separating Earth from a destination planet, a spacecraft may traverse the distance by either moving through a single wormhole or by jumping through any two distinct wormholes together in one maneuver. The order of maneuvers is irrelevant; a route is defined solely by the set of wormhole pairs that are combined. Compute the total number of different routes possible. The result can be expressed directly as n + n·(n‑1)/2, which simplifies to n·(n+1)/2.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Intergalactic Travel Planner"
WHY DOES IT MATTER?
Counting unordered pairings appears in many domains—matching problems, network topology design, and cryptographic key exchanges—so mastering the involution recurrence equips engineers to reason about combinatorial explosion and devise linear‑time solutions.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the state of the problem depends only on the two previous sizes; the (n‑1) factor captures the combinatorial choice of a partner. This eliminates the need for exponential enumeration and enables a simple DP or iterative formula.
REAL-WORLD CONNECTION
Think of a distributed system where nodes can either operate solo or form a direct peer‑to‑peer link. The total number of possible network configurations after a round of link formation follows the same recurrence, illustrating how algorithmic insights translate to system topology planning.
When coding, write the recurrence as a loop with two rolling variables, and always apply the modulo after the multiplication to avoid 64‑bit overflow; using long long (or BigInt) safeguards large intermediate values.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the number of ways to cover a set of n distinct wormholes using either single‑wormhole moves or unordered pairs of wormholes. This is exactly the combinatorial class of involutions (self‑inverse permutations) where each element is either a fixed point or part of a 2‑cycle. The classic recurrence a(n)=a(n‑1)+(n‑1)*a(n‑2) follows from picking a distinguished wormhole: either it stays single (leaving a(n‑1) possibilities) or it pairs with any of the remaining n‑1 wormholes (choose the partner in n‑1 ways) and the rest are arranged in a(n‑2) ways. A naïve enumeration of all subsets or permutations explodes factorially (O(2^n) or worse) and quickly exceeds time limits for n>30. The optimal paradigm is dynamic programming or direct recurrence evaluation, which reduces the exponential blow‑up to linear time by reusing previously computed sub‑results, and can be further compressed to O(1) space because only the two preceding values are needed.
Interview Questions on This Problem
Q1Derive the recurrence relation for the number of routes when you can use single wormholes or unordered pairs, and explain its combinatorial meaning.
Pick a specific wormhole. If it is used alone, the remaining n‑1 wormholes can be arranged in a(n‑1) ways. If it pairs with any of the other n‑1 wormholes, there are (n‑1) choices for the partner and the rest form a(n‑2) ways, giving a(n)=a(n‑1)+(n‑1)*a(n‑2).
Q2How would you compute the answer for n up to 10^6 under modulo 1,000,000,007 while keeping memory usage minimal?
Iterate from i=2 to n, maintaining two variables prev2=a(i‑2) and prev1=a(i‑1). Update cur = (prev1 + (i‑1)*prev2) % MOD, then shift prev2=prev1, prev1=cur. This runs in O(n) time and O(1) extra space.
Q3A startup asks you to extend the problem: each pair can also be a triple jump covering three distinct wormholes. What recurrence would you use?
Let b(n) be the count with singles, pairs, and triples. Choose a distinguished wormhole: single → b(n‑1); pair with any of n‑1 → (n‑1)*b(n‑2); triple with any two of the remaining n‑1 → C(n‑1,2)*b(n‑3). Hence b(n)=b(n‑1)+(n‑1)*b(n‑2)+C(n‑1,2)*b(n‑3).
Examples
Input
1
Output
1
Explanation: Only one wormhole exists, so the only possible route is to travel through it individually. n·(n+1)/2 = 1·2/2 = 1.
Input
3
Output
6
Explanation: Three wormholes give: (i) travel each wormhole separately – 3 distinct single‑wormhole routes; (ii) choose any two wormholes to pair – C(3,2)=3 routes. Total = 3+3 = 6. Using the formula: 3·4/2 = 6.
Input
5
Output
15
Explanation: For five wormholes: single‑wormhole routes = 5. Paired routes = C(5,2)=10. Combined total = 5+10 = 15, matching the formula 5·6/2 = 15.
Constraints
- 1 <= n <= 10^9
- Result fits within a 64‑bit signed integer
- Time complexity O(1)
- Memory usage O(1)
Optimal Approach & Strategy
Use the recurrence a(n)=a(n‑1)+(n‑1)*a(n‑2) and compute iteratively, keeping only the last two values – O(n) time, O(1) space.
Brute Force Approach
Generate every subset of wormholes and every possible pairing, checking each configuration – exponential time (≈O(2^n·n!)).
Verified Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
function countWays(n){
if(n<0) return 0n;
let dp0 = 1n; // dp[0]
if(n===0) return dp0;
let dp1 = 1n; // dp[1]
if(n===1) return dp1;
let cur = 0n;
for(let i=2;i<=n;i++){
cur = dp1 + BigInt(i-1)*dp0;
dp0 = dp1;
dp1 = cur;
}
return dp1;
}
if(input.length){
const n = Number(input);
console.log(countWays(n).toString());
}#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;
cpp_int countWays(int n){
vector<cpp_int> dp(n+2);
dp[0]=1; // empty set
dp[1]=1; // only single
for(int i=2;i<=n;++i){
dp[i]=dp[i-1]+ cpp_int(i-1)*dp[i-2];
}
return dp[n];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
cout<< countWays(n) <<"\n";
return 0;
}import java.io.*;
import java.math.BigInteger;
public class Main {
private static BigInteger countWays(int n) {
if (n < 0) return BigInteger.ZERO;
BigInteger[] dp = new BigInteger[n+2];
dp[0] = BigInteger.ONE;
dp[1] = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1].add(dp[i-2].multiply(BigInteger.valueOf(i-1)));
}
return dp[n];
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line != null && !line.isEmpty()) {
int n = Integer.parseInt(line.trim());
System.out.println(countWays(n));
}
}
}import sys
def count_ways(n):
if n<0:
return 0
dp0, dp1 = 1, 1 # dp[0], dp[1]
if n==0:
return dp0
if n==1:
return dp1
for i in range(2, n+1):
cur = dp1 + (i-1)*dp0
dp0, dp1 = dp1, cur
return dp1
if __name__ == "__main__":
data = sys.stdin.read().strip()
if data:
n = int(data)
print(count_ways(n))const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
function countWays(n){
if(n<0) return 0n;
let dp0 = 1n; // dp[0]
if(n===0) return dp0;
let dp1 = 1n; // dp[1]
if(n===1) return dp1;
let cur = 0n;
for(let i=2;i<=n;i++){
cur = dp1 + BigInt(i-1)*dp0;
dp0 = dp1;
dp1 = cur;
}
return dp1;
}
if(input.length){
const n = Number(input);
console.log(countWays(n).toString());
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.