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);
}