HackerRank Journey to the Moon Problem Solution Yashwant Parihar, May 14, 2023May 14, 2023 In this post, we will solve HackerRank Journey to the Moon Problem Solution. The member states of the UN are planning to send 2 people to the moon. They want them to be from different countries. You will be given a list of pairs of astronaut ID’s. Each pair is made of astronauts from the same country. Determine how many pairs of astronauts from different countries they can choose from.Examplen = 4astronaut [1, 2], [2, 3] =There are 4 astronauts numbered 0 through 3. Astronauts grouped by country are [0] and [1, 2, 3]. There are 3 pairs to choose from: [0, 1], [0,2] and [0,3].Function DescriptionComplete the journeyToMoon function in the editor below.journeyToMoon has the following parameter(s): int n: the number of astronauts int astronaut[p][2]: each element astronaut[i] is a 2 element array that represents the ID’s of two astronauts from the same country Returns– int: the number of valid pairs Input Format The first line contains two integers n and p, the number of astronauts and the number of pairs.Each of the next p lines contains 2 space-separated integers denoting astronaut ID’s of two who share the same nationality. Sample Input 0 5 3 0 1 2 3 0 4 Sample Output 0 6 Explanation 0Persons numbered [0, 1, 4] belong to one country, and those numbered [2, 3] belong to another. The UN has 6 ways of choosing a pair:[0, 2], [0,3], [1, 2], [1, 3], [4, 2], [4, 3] Sample Input 1 4 1 0 2 Sample Output 1 5 Explanation 1Persons numbered [0,2] belong to the same country, but persons 1 and 3 don’t share countries with anyone else. The UN has 5 ways of choosing a pair:[0, 1], [0,3], [1, 2], [1, 3], [2, 3] HackerRank Journey to the Moon Problem Solution Journey to the Moon C Solution #include<stdio.h> #include<stdlib.h> /* list functions */ typedef struct node_n{ int data; struct node_n * next; } edge; typedef struct { int checked; edge * head; } list; void insert(list *l,int data) { edge *new = (edge *) malloc(sizeof(edge)); new->data=data; new->next=l->head; l->head=new; } int delete(list *l) { if(l->head==NULL) return -1; else{ edge *tempNode= l->head; int tempData = l->head->data; l->head=l->head->next; free(tempNode); return tempData; } } /* QueueFunctions */ typedef struct node_n2{ int data; struct node_n2 * next; } node; typedef struct { node * front; node * rear; } queue; int isEmpty(queue *l){ if(l->front==NULL) return 1; else return 0; } //inserts at the end void enqueue(queue *l,int data) { node *new = (node *) malloc(sizeof(node)); new->data=data; new->next=NULL; if(isEmpty(l)) l->front=new; //if queue was empty, connect front else l->rear->next=new; //if queue was not empty, connect previous node with new node l->rear=new; } //deletes from the begining int dequeue(queue *l) { if(l->front==NULL) return -1; else{ node *tempNode= l->front; int tempData = l->front->data; l->front=l->front->next; if(l->front==NULL) l->rear=NULL; //if only one element was in the queue, rear too has to be modified free(tempNode); return tempData; } } /* solution */ /* BFS to explre components of graph and sizes (vertex num of each component) and then mathematical type to find pairs (comp_size*(n-comp_size) and because we count is edge twice in the end we divide by 2)*/ void bfs(list **,int ,list *); int main(){ int n,m,i; scanf("%d %d",&n,&m); list **a=(list **)malloc(sizeof(list *)*(n+1)); if(a==NULL) printf("cannot allocate memory\n"); for(i=0;i<n;i++){ a[i]=(list *)malloc(sizeof(list)); a[i]->checked=0; } for(i=0;i<m;i++){ int v,u; scanf("%d %d",&v,&u); insert(a[v],u); insert(a[u],v); } list *components =(list *)malloc(sizeof(list)); bfs(a,n,components); long long unsigned int counter=0; while(components->head!=NULL){ long long unsigned int omoethneis= delete(components); counter+=omoethneis*(n-omoethneis); } printf("%lld\n",counter/2); return 0; } //returns an updated list (components) with the sizes (num of vertexes) of each component void bfs(list **a,int n,list *components){ queue *frontier=(queue *)malloc(sizeof(queue)); int i=0; while(i<n) { int count=0; enqueue(frontier,i); while(!isEmpty(frontier)){ int v=dequeue(frontier); //printf("examine %d\n",v); count++; //counts nodes on the component a[v]->checked=1; edge *p=a[v]->head; while(p!=NULL){ if(!a[p->data]->checked){ enqueue(frontier,p->data); a[p->data]->checked=1; } p=p->next; } } insert(components,count); while(i<n && a[i]->checked) i++; //printf("end of component, size %d\n",count); } } Journey to the Moon C++ Solution #include <iostream> #include <vector> #include <set> #include <map> inline auto Adj (int u, const std::vector<int>& arr, const std::map<int, std::set<int>>& mp) { std::vector<int> adjl; auto it = mp.find(u); if (it != mp.end()) { for (auto its = it->second.begin(); its != it->second.end(); ++its) { if (arr[*its] < 0) { adjl.emplace_back (*its); } } } return adjl; } auto bfs (int s, std::vector<int>& arr, const std::map<int, std::set<int>>& mp) { int cnt = 1; arr[s] = 0; int level = 1; std::vector<int> frontier (1, s); std::vector<int> next; while (!frontier.empty()) { for (auto it = frontier.begin(); it != frontier.end(); ++it) { auto adjl = Adj (*it, arr, mp); for (auto nit = adjl.begin(); nit != adjl.end(); ++nit) { arr[*nit] = level; next.emplace_back (*nit); ++cnt; } } frontier = std::move (next); ++level; } return cnt; } void addedge (int a, int b, std::map<int, std::set<int>>& mp) { auto it = mp.find(a); if (it != mp.end()) { it->second.emplace (b); } else { std::set<int> st; st.emplace (b); mp.emplace (a, st); } it = mp.find(b); if (it != mp.end()) { it->second.emplace (a); } else { std::set<int> st; st.emplace (a); mp.emplace (b, st); } return; } int main() { int n, k; std::cin >> n; std::cin >> k; std::map<int, std::set<int>> mp; for (int i = 0; i < k; i++) { int a, b; std::cin >> a; std::cin >> b; addedge (a, b, mp); } std::vector<int> arr (n, -1); std::vector<int> clusters; unsigned long res = 0; for (int i = 0; i < n; i++) { if (arr[i] < 0) { auto ans = bfs (i, arr, mp); if (ans > 1) { clusters.emplace_back (ans); } else { ++res; } } } if (res > 0) { clusters.emplace_back (res); res = res * (res-1) / 2; } while (!clusters.empty()) { auto n = clusters.back(); clusters.pop_back(); for (auto it = clusters.begin(); it != clusters.end(); ++it) { res += *it * n; } } std::cout << res << std::endl; return 0; } Journey to the Moon C Sharp Solution using System; using System.Collections.Generic; using System.IO; class Solution { public static int root(int i, int[] arr) { while (i != arr[i]) { i = arr[i]; } return i; } static void Main(string[] args) { string[] tokens = Console.ReadLine().Split(); int n = Convert.ToInt32(tokens[0]); int l = Convert.ToInt32(tokens[1]); int[] arr = new int[n]; int[] sz = new int[n]; int[] depth = new int[n]; for (int i = 0; i < n; i++) { arr[i] = i; sz[i] = 1; depth[i] = 0; } int r1, r2, v1, v2; for (int i = 0; i < l; i++) { tokens = Console.ReadLine().Split(); v1 = Convert.ToInt32(tokens[0]); v2 = Convert.ToInt32(tokens[1]); r1 = root(v1, arr); r2 = root(v2, arr); if (r1 != r2) { if (depth[r1] > depth[r2]) { arr[r2] = r1; sz[r1] += sz[r2]; depth[r2]++; } else { arr[r1] = r2; sz[r2] += sz[r1]; depth[r1]++; } } } // count number of forests int[] sets = new int[n]; int numSets = 0; int numOf1s = 0; int total = 0; for (int i = 0; i < n; i++) { if (arr[i] == i) { if (sz[i] == 1) { numOf1s++; } else { sets[numSets] = i; numSets++; total += sz[i]; } } } long sum = 0; for (int i = 0; i < numSets; i++) { for (int j = i + 1; j < numSets; j++) { sum += ((long)sz[sets[i]] * (long)sz[sets[j]]); } } sum += ((long)numOf1s * ((long)numOf1s - 1) / 2) + ((long)total * (long)numOf1s); Console.WriteLine(sum); Console.ReadLine(); } } Journey to the Moon Java Solution import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.regex.*; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList; class Result { /* * Complete the 'journeyToMoon' function below. * * The function is expected to return an INTEGER. * The function accepts following parameters: * 1. INTEGER n * 2. 2D_INTEGER_ARRAY astronaut */ private static int[] visited; private static int reach(ArrayList<Integer>[] adj, int x, int y) { //write your code here int count = 1; visited[x] = y; for(int a : adj[x]) { if(visited[a]==0) { count += reach(adj,a,y); } } return count; } private static int numberOfComponents(ArrayList<Integer>[] adj, List<Integer> comp) { int result = 0; //write your code here for(int i=0;i<adj.length;i++) { if(visited[i]==0) { result++; comp.add(reach(adj,i,result)); } } return result; } public static long journeyToMoon(int n, List<List<Integer>> astronaut) { // Write your code here ArrayList<Integer>[] adj = new ArrayList[n]; List<Integer> comp = new ArrayList<>(); visited = new int[n]; long pair = 0 ,sum=0; for(int i=0;i<n;i++){ adj[i] = new ArrayList<>(); } for(List<Integer> e : astronaut){ adj[e.get(0)].add(e.get(1)); adj[e.get(1)].add(e.get(0)); } numberOfComponents(adj,comp); for(int c : comp){ pair += c * (n-c-sum); sum += c ; } return pair; } } public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" "); int n = Integer.parseInt(firstMultipleInput[0]); int p = Integer.parseInt(firstMultipleInput[1]); List<List<Integer>> astronaut = new ArrayList<>(); IntStream.range(0, p).forEach(i -> { try { astronaut.add( Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" ")) .map(Integer::parseInt) .collect(toList()) ); } catch (IOException ex) { throw new RuntimeException(ex); } }); long result = Result.journeyToMoon(n, astronaut); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); bufferedReader.close(); bufferedWriter.close(); } } Journey to the Moon JavaScript Solution let _ = require('underscore'); function processData(input) { let [[n, i], ...lines] = input.split('\n').map(l => l.split(' ').map(Number)); let sets = [], set; do { set = new Set(...lines.splice(0, 1)); let p1, p2; do { [p1, p2] = _.partition(lines, (p) => set.has(p[0]) || set.has(p[1])); lines = p2; if (p1.length) { p1.forEach( p => { set.add(p[0]); set.add(p[1]); } ) } } while (p1.length); sets.push(set); } while (lines.length); sets = sets.map(s => s.size); let diff = n - sets.reduce((a, b) => a + b); if (diff) { sets.push(diff); } let r = 0; for (let i = 0; i < sets.length; i++) { for (let j = i + 1; j < sets.length; j++) { r += sets[i] * sets[j]; } } if (diff) { r += (diff * (diff - 1)) / 2; } console.log(r); } process.stdin.resume(); process.stdin.setEncoding("ascii"); _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); }); Journey to the Moon Python Solution class Graph: def __init__(self, edges, vertex_count): self.edges = edges self.vertexes = list(range(vertex_count)) def get_components_sizes(self): n = len(self.vertexes) color = list(range(n)) components = {i:[int(i)] for i in range(n)} for edge in self.edges: v1, v2 = edge c1, c2 = color[v1], color[v2] if c1 == c2: continue else: components[c1] += components[c2] for v in components[c2]: color[v] = c1 components.pop(c2) sizes = [len(components[key]) for key in components.keys()] return sizes astronauts_count, relations_count = [int(i) for i in input().split()] relations = [] for t in range(relations_count): relations.append(tuple([int(i) for i in input().split()])) g = Graph(edges=relations, vertex_count=astronauts_count) countries_sizes = g.get_components_sizes() count_ways = astronauts_count ** 2 for country_size in countries_sizes: count_ways -= country_size ** 2 count_ways //= 2 print(count_ways) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython