Cerinta completa

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.

Example


There are astronauts numbered through . Astronauts grouped by country are and . There are pairs to choose from: and .

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 is a 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 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

Sample Input 0

5 3
0 1
2 3
0 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 1
0 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:

Limbajul de programare folosit: java8

Cod:

//Problem: https://www.hackerrank.com/challenges/journey-to-the-moon
//Java 8
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int I = input.nextInt(); 
        
        int[] astronauts = new int[N];                       //directed graph
        HashMap<Integer,Integer> countries = new HashMap<>();//Will be used as a bag
        
        

        //We will use q and qq for our loop variables because I has already been used
        
        //We intialize our array with each node as it's own representative
        Arrays.fill(astronauts, -1);
        
        //Converts our array into a directed graph that points from one astronaut to another in the same country until
        //you reach the last astronaut with a pointer to itself
        for(int q = 0; q < I; q++)
        {
            int parent = input.nextInt();
            int child = input.nextInt();
            
            
            astronauts[parent] = (astronauts[parent] == -1) ? parent : astronauts[parent];
            astronauts[child] = (astronauts[child] == -1) ? child : astronauts[child];
             
            //Joining two graphs
            int oldRep = astronauts[child];
            astronauts[child] = astronauts[parent];

            //Updates pointers when combining two graphs with different representatives
            for(int qq = 0; qq < N; qq++)
            {
                if(astronauts[qq] == oldRep)
                {
                    astronauts[qq] = astronauts[parent];
                }
            }
        }//for
        
        /*  This builds a Hashmap of our astronauts based on country using our directed graph.
        
        Using a hasmap here instead of going straight to an array is a design decision based on the assumption that
        the majority of cases will have multiple items in a set, so we reduce our space to 2*(number of countries) compared to 
        N size array which will only be smaller in the case where more than half of the astronauts are the only astronaut within 
        their country*/
        
        for(int person : astronauts)
        {
            if(countries.get(person) == null)
            {
                countries.put(person, 1);
            }
            else
            {
                countries.put(person, countries.get(person) + 1);
            }
        }
        
        
        //Move our values into an array where we can access them easier
        int[] tmp = new int[countries.size()];
        
        long lonelyAstronauts = 0; //Astronauts who are the only one in their country
                                  //If we do have lonely astronauts then the last index will be 0
                                  //#We store this as long because we will use it in a long calc later
        int j = 0;
        for(Map.Entry<Integer,Integer> country : countries.entrySet())
        {            
            if(country.getKey() == -1)
            {
                lonelyAstronauts = (long) country.getValue();
                continue;
            }
            
            tmp[j] = country.getValue();
            j++;
        }
        
        
        
        
        //Calculate possible combinations based on our sets //Stored as long because combinations of 10^5 can get large
        long combinations = 0;
        
        for(int q = 0; q < tmp.length; q++)
        {
            for(int qq = q+1; qq < tmp.length; qq++)
            {
                combinations += tmp[q] * tmp[qq];
            }
        }
        
        //Added the increased combinations as a result of our single astronaut countries
        if(lonelyAstronauts != 0)
        {
            combinations += (lonelyAstronauts * (N-lonelyAstronauts)) + (((lonelyAstronauts-1)*lonelyAstronauts)/2);
        }
        
        System.out.println(combinations);
    }
}

Scor obtinut: 1.0

Submission ID: 464602910

Link challenge: https://www.hackerrank.com/challenges/journey-to-the-moon/problem

Journey to the Moon