Hackerrank Journey to the Moon Solution

The member states of the UN are planning to send  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.

For example, we have the following data on 2 pairs of astronauts, and 4 astronauts total, numbered  through .

1   2
2   3


Astronauts by country are  and .  There are  pairs to choose from:  and .

Function Description

Complete the journeyToMoon function in the editor below.  It should return an integer that represents the number of valid pairs that can be formed.

journeyToMoon has the following parameter(s):

• n: an integer that denotes the number of astronauts
• astronaut: a 2D array where each element  is a  element integer array that represents the ID's of two astronauts from the same country

Input Format.

The first line contains two integers  and , the number of astronauts and the number of pairs.
Each of the next  lines contains  space-separated integers denoting astronaut ID's of two who share the same nationality.

Constraints.

Output Format.

An integer that denotes the number of ways to choose a pair of astronauts from different coutries.

Sample Input 0.5 30 12 30 4

Sample Output 0.6

Explanation 0.

Persons numbered  belong to one country, and those numbered  belong to another. The UN has  ways of choosing a pair:

Sample Input 1.4 10 2

Sample Output 1. 5

Explanation 1.

Persons numbered   belong to the same country, but persons  and  don't share countries with anyone else.  The UN has  ways of choosing a pair:

Solution in java8

Approach 1.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {

public static void main(String[] args) throws InterruptedException {
Scanner sc = new Scanner(System.in);
int N, P;
N = sc.nextInt();
P = sc.nextInt();

Graph g = new Graph(N);
for (int i = 0; i < P; i++) {
g.addEdge(sc.nextInt(), sc.nextInt());
}
System.out.println(g.solutions1());
sc.close();
}
}

class Graph{
static int Vm;
static boolean visited[];
HashMap<Integer, ArrayList<Integer>> graph;
Graph(int Vm){
this.Vm = Vm;
visited = new boolean[Vm];
graph = new HashMap<>();
for (int i = 0; i < Vm; i++) {
graph.put(i, new ArrayList<>());
}
}

public void addEdge(int s, int d) {
graph.get(s).add(d);
graph.get(d).add(s);
}

public int DFSG(int s) {
int count = 1;
visited[s] = true;
for (Integer i : graph.get(s)) {
if(!visited[i]) {
count+=DFSG(i);
}
}
return count;
}

public ArrayList<Integer> traversal(){
ArrayList<Integer> cSizes = new ArrayList<>();
for (int i = 0; i < visited.length; i++) {
if(!visited[i])
cSizes.add(DFSG(i));
}
return cSizes;
}

public long solutions1() {
ArrayList<Integer> cSizes = traversal();
long sum = 0, res=0;
for(int size : cSizes){
res += sum*size;
sum += size;
}
return res;
}
}

Approach 2.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
static void init(int size[],int n,int arr[])
{
for(int i=0;i<n;i++)
{
size[i] = 1;
arr[i] = i;
}
}
static int root(int t,int a[])
{
while(a[t]!=t)
{
a[t] = a[a[t]];
t = a[t];
}
return t;
}

static void union(int a, int b, int Size[],int arr[])
{
int root_a = root(a,arr);
int root_b = root(b,arr);
if(root_a==root_b)
return;
if(Size[root_a]<Size[root_b])
{
arr[root_a] = arr[root_b];
Size[root_b] += Size[root_a];
Size[root_a] = 0;
}
else
{
arr[root_b] = arr[root_a];
Size[root_a] += Size[root_b];
Size[root_b] = 0;
}
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int p = in.nextInt();
long result;
int Size[] = new int[n+1];
int arr[] = new int[n+1];
init(Size,n,arr);
for(int i=0;i<p;i++)
{
int x = in.nextInt();
int y = in.nextInt();
union(x, y, Size,arr);
}
long p_res = 0;
long s_res = 0;
for(int i=0;i<n;i++)
{
p_res = p_res+Size[i];
s_res = s_res+(Size[i]*Size[i]);
}
result = ((p_res*p_res)-s_res)/2;
System.out.println(result);
in.close();
}
}


Approach 3.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class Graph{
public int vert;
public Graph next;

public Graph addEdge(Graph current, int vertex){
Graph head = new Graph();
head.vert = vertex;
head.next = current;

return head;
}
}

public class Solution {

static long journeyToMoon(int n, Graph[] list) {
boolean[] visit = new boolean[n];
Stack<Integer> st = new Stack<Integer>();
ArrayList<Integer> arr = new ArrayList<Integer>();
for(int i = 0; i < n; i++){
int count = 0;
//boolean f = false;
st.push(i);
while(!st.empty()){
int tmp = st.pop();
if(!visit[tmp]){
count++;
//System.out.println(tmp);
visit[tmp] = true;
//f = true;
Graph temp = list[tmp];
while(temp != null){
st.push(temp.vert);
temp = temp.next;
}
}
}
//if(f)
arr.add(count);
//else
//  arr.add(1);
}
/*  for(int z : arr)
System.out.print(z + " ");
System.out.println("");    */

long ans = 0;
long sum = arr.get(0);
for(int i = 1; i < arr.size(); i++){
ans += sum * arr.get(i);
sum += arr.get(i);
}

return ans;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int p = in.nextInt();
Graph[] list = new Graph[n];
Graph temp = new Graph();

for(int i = 0; i < p; i++){
int v1 = in.nextInt();
int v2 = in.nextInt();

list[v1] = temp.addEdge(list[v1], v2);
list[v2] = temp.addEdge(list[v2], v1);
}
in.close();

System.out.println(journeyToMoon(n, list));
}
}


Solution in python3

Approach 1.

N, P = tuple(map(int, input().strip().split(' ')))

sets = [{i} for i in range(N)]

arr = [i for i in range(N)] #sets[arr[i]] contains i

for i in range(P):
a, b = tuple(map(int, input().strip().split(' ')))
if a not in sets[arr[b]]:
#union the sets
u = sets[arr[a]] | sets[arr[b]]
sets[a] = u #store the union at sets[a]
for j in u: #pointers to a
if j!=a:
sets[j]=set()
arr[j]=a
total = 0
non_singles = 0
for i in range(N):
#print(sets[arr[i]], sets[i])
L = len(sets[i])
if L>1: #non-single set with length L
non_singles += L
#add pairs with first person in the subset
total += L*(N-L)

#singles = N - non_singles
#add pairs with first person in the set of singles
total = total + (N-non_singles)*(N-1)

#remove double counting
total = total//2
print(total)


Approach 2.

#!/bin/python3

import math
import os
import random
import re
import sys

sys.setrecursionlimit(1500)
def dfs(graph,same,i):
same[i] = True
ans = 1
for j in graph[i]:
if (same[j] == False):
ans += dfs(graph,same,j)
return ans
# Complete the journeyToMoon function below.
def journeyToMoon(n, astronaut):
graph = {}
for i in range(n):
graph[i] = []
for v in astronaut:
graph[v[0]].append(v[1])
graph[v[1]].append(v[0])

countries = n*(n-1)//2
same = [False]*n
for i in range(n):
if (same[i] == False):
x = dfs(graph,same,i)
countries -= x*(x-1)//2

return countries

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

np = input().split()

n = int(np[0])

p = int(np[1])

astronaut = []

for _ in range(p):
astronaut.append(list(map(int, input().rstrip().split())))

result = journeyToMoon(n, astronaut)

fptr.write(str(result) + '\n')

fptr.close()


Approach 3.

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import Counter

# Complete the journeyToMoon function below.
def journeyToMoon(n, astronaut):

def getRoot(a2):
tmp = a2
while d[tmp] != tmp:
tmp = d[tmp]

root = tmp
while a2 != d[a2]:
t = d[a2]
d[a2] = root
a2 = t
return root

d = {}
for a1,a2 in astronaut:
if a1 not in d:
d[a1] = a1
if a2 not in d:
d[a2] = a2

root1 = getRoot(a1)
root2 = getRoot(a2)
if root1 != root2:
d[root1] = root2

c = 0

for i in range(n):
if i not in d:
c += 1
else:
d[i] = getRoot(i)

arr =  list(Counter(d.values()).values())

res = 0
if c:
res = c*(c-1)//2

for i in range(0,len(arr)):
res += (arr[i]*c)
for j in range(i+1,len(arr)):
res += (arr[i]* arr[j])

return res

if __name__ == '__main__':

fptr = open(os.environ['OUTPUT_PATH'], 'w')

np = input().split()

n = int(np[0])

p = int(np[1])

astronaut = []

for _ in range(p):
astronaut.append(list(map(int, input().rstrip().split())))

result = journeyToMoon(n, astronaut)

fptr.write(str(result) + '\n')

fptr.close()


Solution in cpp

Approach 1.

#include<iostream>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;

int N,K,A,B,C[100000],NC;
set<int> G[100000];

queue<int> Q;
set<int>::iterator it;
long long colour(int root) {
C[root] = ++NC;
Q.push(root);
long long result = 1;
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(it = G[u].begin(); it != G[u].end(); it++) {
int v = *it;
if(C[v]==0) {
C[v] = NC;
result++;
Q.push(v);
}
}
}
return result;
}

int main() {
cin >> N >> K;
for(int i = 0; i < K; i++) {
cin >> A >> B;
G[A].insert(B);
G[B].insert(A);
}
long long result = 0;
long long sum = 0;
for(int i = 0; i < N; i++)
if(C[i]==0) {
long long x = colour(i);
result += sum*x;
sum += x;
}
cout << result << endl;
}

Approach 2.

#include<bits/stdc++.h>

using namespace std; // }}}

int main()
{
int N, I;
cin >> N >> I;
vector<vector<int> > pairs(N);
queue < int > q;
for (int i = 0; i < I; ++i) {
int a, b;
cin >> a >> b;
pairs[a].push_back(b);
pairs[b].push_back(a);
}

long long result = 1;

vector<int> visited(N);
for(int i=0;i<N;i++)
{
visited[i]=0;
}

for(int i=0;i<N;i++)
{long long ans=0;
if(!visited[i])
{
ans=1;
q.push(i);
visited[i]=1;
while(!q.empty())
{
int node = q.front();
q.pop();
int l=pairs[node].size();
for(int j =0 ; j<l;j++)
{
int next = pairs[node][j];
if(!visited[next])
{
visited[next]=1;
q.push(next);
ans++;
}
}
}
}
result=result+(ans*(N-ans));
}

/** Write code to compute the result using N,I,pairs **/
result=result/2;

cout << result << endl;
return 0;
}


Approach 3.

#include<bits/stdc++.h>
#define lli long long int
using namespace std;
vector<lli> v[1000000];
lli visited[1000000];
lli mul[1000000];
lli mul1[1000000];
lli mulass[10000000];
void dfs(lli a,lli b)
{
visited[a]=b;
for(lli i=0;i<v[a].size();i++)
{
if(visited[v[a][i]]==0)
dfs(v[a][i],b);
}
}

int main()
{
lli n,m;
scanf("%lld%lld",&n,&m);
for(lli i=0;i<=n;i++)
{
visited[i]=0;
mul[i]=0;
mulass[i]=0;
v[i].clear();
}
for(lli i=0;i<m;i++)
{
lli a,b;
scanf("%lld%lld",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
lli x=1;
for(lli i=0;i<n;i++)
{
if(visited[i]==0)
{
dfs(i,x);
x++;
}
}

for(lli i=0;i<n;i++)
{
mul[visited[i]]++;
}
lli ans=0,j=1;
for(lli i=1;i<=x;i++)
{
if(mul[i]==0)
continue;
else
{
mul1[j]=mul[i];
mulass[j]=mulass[j-1]+mul1[j];
j++;
}
}
/*for(lli i=0;i<j;i++)
printf("%lld ",mulass[i]);*/
for(lli i=1;i<j;i++)
{
lli z=(mulass[j-1]-mulass[i]);
if(z<0)
z=0;
ans=ans+mul1[i]*z;
}
printf("%lld\n",ans);
}