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

Sample Output 0

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

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]

Table of Contents

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)