Journey to the Moon – Hackerrank Challenge – Java Solution
This is the java solution for the Hackerrank problem – Journey to the Moon – Hackerrank Challenge – Java Solution.
Source – Ryan Fehr’s repository.
//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 HashMapcountries = 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 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); } }