Journey to the Moon
Problem Statement
There are N astronauts numbered 0 to N-1. Some astronauts are from the same country and are given as pairs. Two astronauts can be sent to the moon only if they are from different countries. Find the number of valid pairs.
Example:
- Input:
N = 5, pairs = [(0,1), (2,3), (0,4)] - Output:
6(Valid pairs: (0,2), (0,3), (1,2), (1,3), (4,2), (4,3))
Noob-Friendly Explanation
Imagine NASA wants to send two astronauts to the moon. But they have a rule: the two astronauts must be from different countries. You're given a list of astronauts and told which ones are from the same country (they're "paired" together). Astronauts from the same country form a group.
You need to count how many ways you can pick two astronauts from different groups. First, find all the country groups, then count pairs across different groups.
Approach 1: Brute Force
Intuition
Find all connected components (countries) using BFS/DFS. Then for every pair of astronauts, check if they belong to different components.
Algorithm
- Build the graph from pairs.
- Find connected components using BFS/DFS.
- For each pair (i, j) where i < j, check if they're in different components.
- Count valid pairs.
import java.util.*;
public class JourneyMoonBrute {
public static long countPairs(int n, int[][] pairs) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : pairs) {
adj.get(p[0]).add(p[1]);
adj.get(p[1]).add(p[0]);
}
// Find component id for each astronaut
int[] compId = new int[n];
Arrays.fill(compId, -1);
int compCount = 0;
for (int i = 0; i < n; i++) {
if (compId[i] == -1) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
compId[i] = compCount;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neigh : adj.get(node)) {
if (compId[neigh] == -1) {
compId[neigh] = compCount;
queue.offer(neigh);
}
}
}
compCount++;
}
}
// Count pairs from different components
long count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (compId[i] != compId[j]) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int n = 5;
int[][] pairs = {{0,1},{2,3},{0,4}};
System.out.println("Valid pairs: " + countPairs(n, pairs));
}
}Complexity Analysis
- Time Complexity: O(N² + P) - BFS is O(N + P), pair counting is O(N²)
- Space Complexity: O(N + P) - adjacency list and component IDs
Approach 2: Optimal (Union-Find + Math)
Intuition
Use Union-Find to group astronauts by country. Then, instead of checking all pairs, use math: total pairs = N*(N-1)/2. Subtract pairs from the same country. Or equivalently, for each component of size s, the number of pairs within it is s*(s-1)/2. Answer = total pairs - same-country pairs.
Alternatively, track component sizes and use the formula: sum of size[i] * (N - size[i]) / 2 for all components gives the pairs from different countries.
Algorithm
- Use Union-Find with path compression and union by rank.
- Process all pairs to union astronauts from the same country.
- Calculate component sizes.
- Answer = total_pairs - sum of (size_i * (size_i - 1) / 2) for each component.
import java.util.*;
public class JourneyMoonOptimal {
static int[] parent, rank;
static int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
static void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
}
public static long countPairs(int n, int[][] pairs) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int[] p : pairs) {
union(p[0], p[1]);
}
// Count component sizes
Map<Integer, Integer> sizes = new HashMap<>();
for (int i = 0; i < n; i++) {
int root = find(i);
sizes.put(root, sizes.getOrDefault(root, 0) + 1);
}
long totalPairs = (long) n * (n - 1) / 2;
long samePairs = 0;
for (int size : sizes.values()) {
samePairs += (long) size * (size - 1) / 2;
}
return totalPairs - samePairs;
}
public static void main(String[] args) {
int n = 5;
int[][] pairs = {{0,1},{2,3},{0,4}};
System.out.println("Valid pairs: " + countPairs(n, pairs));
}
}Complexity Analysis
- Time Complexity: O(N + P) - Union-Find operations are nearly O(1) amortized with path compression
- Space Complexity: O(N + P) - for parent, rank arrays and input storage