Journey to the Moon - Hackerrank Problem Solution

Journey to the Moon

Hackerrank Problem Solution

Journey to the Moon - Hackerrank Solution

PROBLEM STATEMENT

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: an integer that denotes 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:

---

SOLUTION

from collections import defaultdict def group_team(astronaut): country = defaultdict(set) for i,(a,b) in enumerate(astronaut): country[i].update([a,b]) while country: i = list(country.keys())[0] x = country[i] pops = [k for k,v in country.items() if v & x] if len(pops) ==1: country.pop(i) yield x else: for p in pops: x = x | country.pop(p) country[i] = x def journeyToMoon(n, astronaut): arr = [len(i) for i in group_team(astronaut)] s = sum(arr) c = 0 for i in range(s,n): arr.append(1) s+=1 for i in arr: s-=i c+= i*s return c n,p = map(int,input().split()) astronaut = [list(map(int,input().split())) for _ in range(p)] print(journeyToMoon(n, astronaut))

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.