- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a list of preferences for n(even) different friends. For each person i, the preferences[i] holds a list of friends sorted in the order of preference. So, a friend earlier in the list is more preferred than a friend later in the list. The friends in each list are numbered by integers from 0 to n-1. All of the friends are divided into different pairs. where pairs[i] = [xi, yi] represents xi is paired with yi and/or yi is paired with xi. But a friend x is unhappy if x is paired with y and there exists a friend u who is also paired with v but −

- x prefers u over y, and
- u prefers x over v.

We have to find the number of unhappy friends.

So, if the input is like preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] pairs = [[0, 1], [2, 3]], then the output will be 2 because first friend is unhappy because person 1 is paired with person 0 but prefers person 3 over person 0, and person 3 prefers person 1 over person 2. And friend 3 is unhappy because person 3 is paired with person 2 but prefers person 1 over person 2, and person 1 prefers person 3 over person 0.

To solve this, we will follow these steps −

- graph := an adjacency list to make graph, initially empty
- for each pair (s, e) in pairs, do
- for each pref in preferences[s], do
- if pref is same as end, then
- come out from loop

- graph[s, pref] := 1

- if pref is same as end, then
- for each pref in preferences[e], do
- if pref is same as start, then
- come out from loop

- graph[e, pref] := 1

- if pref is same as start, then

- for each pref in preferences[s], do
- unhappy := 0
- for each pair (s, e) in pairs, do
- for each pref in graph[s], do
- if graph[pref][s] is not empty, then
- unhappy := unhappy + 1
- come out from loop

- if graph[pref][s] is not empty, then
- for each pref in graph[end], do
- if graph[pref][e] is not empty, then
- unhappy := unhappy + 1
- come out from loop

- if graph[pref][e] is not empty, then

- for each pref in graph[s], do
- return unhappy

Let us see the following implementation to get better understanding −

from collections import defaultdict def solve(preferences, pairs): graph = defaultdict(dict) for start, end in pairs: for pref in preferences[start]: if pref == end: break graph[start][pref] = 1 for pref in preferences[end]: if pref == start: break graph[end][pref] = 1 unhappy = 0 for start, end in pairs: for pref in graph[start]: if graph[pref].get(start, None): unhappy += 1 break for pref in graph[end]: if graph[pref].get(end, None): unhappy += 1 break return unhappy preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] pairs = [[0, 1], [2, 3]] print(solve(preferences, pairs))

[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], [[0, 1], [2, 3]]

2

- Related Questions & Answers
- Program to find number of friend groups in a set of friends connections in Python
- Program to count number of palindromic substrings in Python
- Program to count number of homogenous substrings in Python
- Program to count number of nice subarrays in Python
- Program to count the number of consistent strings in Python
- Python program to count number of substring present in string
- Program to count number of possible humble matrices in Python
- Program to count number of matches played in tournament in Python
- Program to count number of distinct substrings in s in Python
- Program to count number of stepping numbers of n digits in python
- Program to count number of common divisors of two numbers in Python
- Python Program to Count trailing zeroes in factorial of a number
- Python Program to Count Number of Leaf Node in a Tree
- Python Program to Count Number of Lowercase Characters in a String
- Program to count number of BST with n nodes in Python

Advertisements