HackerRank Journey to the Moon Problem Solution
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.
Example
n = 4
astronaut [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 Description
Complete 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 0
Persons 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 1
Persons 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]
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)