Log inSign up
mediumHackerRankNot Started

Journey to the Moon

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on HackerRank
Lesson

Problem Statement

### Problem Statement

The member states of the UN are planning to send 2 astronauts to the moon. They want them from different countries.

You will be given the total number of astronauts n (numbered from 0 to n - 1) and a list of pairs of astronaut IDs astronaut where each pair [a, b] indicates that astronaut a and astronaut b are from the same country.

Determine how many valid pairs of astronauts from different countries can be chosen.

Note that nationality is transitive: if astronaut a and b share a country, and b and c share a country, then a, b, and c all belong to the same country.

---

### Examples

Example 1: ``text Input: n = 5, astronaut = [[0, 1], [2, 3], [0, 4]] Output: 6 Explanation: Country 1: {0, 1, 4} (size 3) Country 2: {2, 3} (size 2) Astronaut pairs from different countries: (0, 2), (0, 3), (1, 2), (1, 3), (4, 2), (4, 3) Total valid pairs = 3 * 2 = 6.

Example 2: ``text Input: n = 4, astronaut = [[0, 2]] Output: 5 Explanation: Country 1: {0, 2} (size 2) Country 2: {1} (size 1) Country 3: {3} (size 1) Valid pairs: - Country 1 & Country 2: 2 * 1 = 2 - Country 1 & Country 3: 2 * 1 = 2 - Country 2 & Country 3: 1 * 1 = 1 Total = 2 + 2 + 1 = 5.

---

### Constraints - 1 <= n <= 10^5 - 0 <= p <= 10^4 (where p is the number of pairs in astronaut) - astronaut[i].length == 2 - 0 <= astronaut[i][j] < n - Output can exceed 32-bit integer limits (up to 10^{10}); use 64-bit integers (long long / long).

Constraints:

  • 1 <= n <= 105
  • 0 <= p <= 104
  • astronaut[i].length == 2
  • 0 <= astronaut[i][j] < n
  • Result requires 64-bit integer

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Extract sizes of connected components using graph traversal and DSU.
  • Apply combinatorial complement counting to solve pairwise selection in O(k) time instead of O(k2).
  • Prevent 32-bit integer arithmetic overflow on large graphs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Select pairs of elements from different equivalence classes / connected components
  • Transitive relationship forming connected clusters
  • Combinatorial pairs across graph components

Algorithmic Decision Tree:

  • Model as connected components via DFS/BFS or DSU.
  • Compute sizes of all connected components s_1, s_2, ..., s_k.
  • Apply totalPairs = (n * (n - 1)) / 2 - sum(s_i * (s_i - 1) / 2).

Connected Patterns:

Number of Connected ComponentsRedundant ConnectionCount Unreachable Pairs of Nodes in an Undirected Graph

1. BFS Component Sizing with Double Loop Combinations

Intuition

Traverse the graph with BFS starting at each unvisited node to count component sizes. After gathering the list of component sizes, iterate with two nested loops for i in 0..c: for j in i+1..c: pairs += size[i] * size[j].

Algorithm

  1. Build adjacency list for all n astronauts.
  2. Initialize visited array of size n to false.
  3. Initialize componentSizes list.
  4. Loop i from 0 to n - 1:
  5. If !visited[i]:
  6. Run BFS from i, counting nodes in this component.
  7. componentSizes.push(count).
  8. Initialize totalPairs = 0.
  9. For i from 0 to componentSizes.length - 1:
  10. For j from i + 1 to componentSizes.length - 1:
  11. totalPairs += componentSizes[i] * componentSizes[j].
  12. Return totalPairs.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 long long journeyToMoon(int n, std::vector<std::vector<int>>& astronaut) {
8 std::vector<std::vector<int>> adj(n);
9 for (const auto& p : astronaut) {
10 adj[p[0]].push_back(p[1]);
11 adj[p[1]].push_back(p[0]);
12 }
13
14 std::vector<bool> visited(n, false);
15 std::vector<long long> compSizes;
16
17 for (int i = 0; i < n; ++i) {
18 if (!visited[i]) {
19 long long count = 0;
20 std::queue<int> q;
21 q.push(i);
22 visited[i] = true;
23
24 while (!q.empty()) {
25 int curr = q.front();
26 q.pop();
27 count++;
28
29 for (int neighbor : adj[curr]) {
30 if (!visited[neighbor]) {
31 visited[neighbor] = true;
32 q.push(neighbor);
33 }
34 }
35 }
36 compSizes.push_back(count);
37 }
38 }
39
40 long long totalPairs = 0;
41 int k = compSizes.size();
42 for (int i = 0; i < k; ++i) {
43 for (int j = i + 1; j < k; ++j) {
44 totalPairs += compSizes[i] * compSizes[j];
45 }
46 }
47
48 return totalPairs;
49 }
50};
51
52int main() {
53 Solution sol;
54 std::vector<std::vector<int>> pairs = {{0, 1}, {2, 3}, {0, 4}};
55 std::cout << "Pairs: " << sol.journeyToMoon(5, pairs) << " (Expected: 6)\n";
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(V + E + k^2)
  • Space complexity: O(V + E)

2. Disjoint Set Union (DSU / Union-Find) with Running Prefix Sum

Intuition

Instead of building an adjacency list, maintain set sizes directly inside DSU (size[root]). After unioning all given pairs, identify component roots and calculate total pairs using running prefix sums in a single pass.

Algorithm

  1. Initialize DSU with size tracking: size[i] = 1.
  2. For each pair [u, v] in astronaut: dsu.unite(u, v).
  3. Collect component sizes for all distinct roots (find(i) == i).
  4. Compute pairs using running sum: for size in compSizes: ans += size * currentSum; currentSum += size.
  5. Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class DSU {
5public:
6 std::vector<int> parent;
7 std::vector<long long> compSize;
8 DSU(int n) : parent(n), compSize(n, 1) {
9 for (int i = 0; i < n; ++i) parent[i] = i;
10 }
11 int find(int i) {
12 if (parent[i] == i) return i;
13 return parent[i] = find(parent[i]);
14 }
15 void unite(int i, int j) {
16 int rootI = find(i);
17 int rootJ = find(j);
18 if (rootI != rootJ) {
19 if (compSize[rootI] < compSize[rootJ]) std::swap(rootI, rootJ);
20 parent[rootJ] = rootI;
21 compSize[rootI] += compSize[rootJ];
22 }
23 }
24};
25
26class Solution {
27public:
28 long long journeyToMoon(int n, std::vector<std::vector<int>>& astronaut) {
29 DSU dsu(n);
30 for (const auto& p : astronaut) {
31 dsu.unite(p[0], p[1]);
32 }
33
34 long long totalPairs = 0;
35 long long currentSum = 0;
36
37 for (int i = 0; i < n; ++i) {
38 if (dsu.find(i) == i) {
39 long long s = dsu.compSize[i];
40 totalPairs += s * currentSum;
41 currentSum += s;
42 }
43 }
44
45 return totalPairs;
46 }
47};
48
49int main() {
50 Solution sol;
51 std::vector<std::vector<int>> pairs = {{0, 1}, {2, 3}, {0, 4}};
52 std::cout << "DSU Pairs: " << sol.journeyToMoon(5, pairs) << " (Expected: 6)\n";
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(n + p * alpha(n))
  • Space complexity: O(n)

3. Canonical DFS Component Sizing with Combinatorial Complement (Optimal)

Intuition

The cleanest mathematical formulation. Total pairs of any two astronauts is totalAll = n * (n - 1) / 2. The only invalid pairs are two astronauts from the same country (sameCountry = sum(s * (s - 1) / 2)). The answer is simply totalAll - sameCountry. Each node and edge is visited exactly once.

Algorithm

  1. Build adjacency list adj for n astronauts.
  2. Initialize boolean visited array of size n to false.
  3. Define dfs(u):
  4. visited[u] = true.
  5. size = 1.
  6. For each neighbor v in adj[u]:
  7. If !visited[v]: size += dfs(v).
  8. Return size.
  9. Initialize sameCountryPairs = 0.
  10. Loop i from 0 to n - 1:
  11. If !visited[i]:
  12. s = dfs(i).
  13. sameCountryPairs += (s * (s - 1)) / 2.
  14. Compute totalPossiblePairs = ((long long)n * (n - 1)) / 2.
  15. Return totalPossiblePairs - sameCountryPairs.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 long long dfs(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
6 visited[u] = true;
7 long long size = 1;
8
9 for (int v : adj[u]) {
10 if (!visited[v]) {
11 size += dfs(v, adj, visited);
12 }
13 }
14 return size;
15 }
16public:
17 long long journeyToMoon(int n, std::vector<std::vector<int>>& astronaut) {
18 std::vector<std::vector<int>> adj(n);
19 for (const auto& p : astronaut) {
20 adj[p[0]].push_back(p[1]);
21 adj[p[1]].push_back(p[0]);
22 }
23
24 std::vector<bool> visited(n, false);
25 long long sameCountryPairs = 0;
26
27 for (int i = 0; i < n; ++i) {
28 if (!visited[i]) {
29 long long s = dfs(i, adj, visited);
30 sameCountryPairs += (s * (s - 1)) / 2;
31 }
32 }
33
34 long long totalAll = (1LL * n * (n - 1)) / 2;
35 return totalAll - sameCountryPairs;
36 }
37};
38
39int main() {
40 Solution sol;
41 std::vector<std::vector<int>> pairs = {{0, 1}, {2, 3}, {0, 4}};
42 std::cout << "Canonical DFS Pairs: " << sol.journeyToMoon(5, pairs) << " (Expected: 6)\n";
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V + E)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BFS with Double Loop CombinationsO(V + E + k^2)O(V + E)Discovers component sizes via BFS, then adds pairs using nested loops.Nested loop over component count
2.DSU with Running Prefix SumO(n + p * alpha(n))O(n)Maintains size in DSU; computes pairs in one pass using running prefix sum.Union-find operations
3.Canonical DFS with Combinatorial ComplementOptimalO(V + E)O(V + E)Computes total C(n, 2) and subtracts same-country pairs C(s_i, 2).Call stack depth

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using 32-bit integers, causing negative overflow when computing n * (n - 1) / 2.

Pitfall 2:

Forgetting about isolated nodes (astronauts with no edges), missing components of size 1.

Pitfall 3:

Using an O(k2) nested loop over component sizes, timing out when k is large.

Crucial Edge Cases to Validate:

  • No pairs given (astronaut = []) — All n astronauts are from different countries; answer is C(n, 2) = n * (n - 1) / 2.
  • All astronauts belong to the same country (single component of size n) — sameCountryPairs = C(n, 2), answer is C(n, 2) - C(n, 2) = 0.
  • Large graph (n = 10^5) — 64-bit arithmetic prevents integer overflow during multiplication.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the complement formula upfront: 'Total Valid Pairs = Total Possible Pairs - Same Country Pairs.'
  2. Explicitly mention 64-bit types (long long in C++, long in Java) to show attention to overflow bounds.
  3. Note that isolated nodes naturally have s = 1, contributing s * (s - 1) / 2 = 0 invalid pairs.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the combinatorial complement formula C(n, 2) - sum(C(s_i, 2)) preferable over double-looping all pairs of components?

2.Why is 64-bit integer arithmetic required for this problem?

3.What happens to astronauts who are not mentioned in any pair?

Back to DSA Sheet