3

Minimum and Maximum number of pairs in m teams of n people

 2 years ago
source link: https://www.geeksforgeeks.org/minimum-and-maximum-number-of-pairs-in-m-teams-of-n-people/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Improve Article

Minimum and Maximum number of pairs in m teams of n people

  • Difficulty Level : Medium
  • Last Updated : 31 Mar, 2021

There are npeople which are to be grouped into exactly mteams such that there is at least one person in each team. All members of a team are friends with each other. Find the minimum and maximum no. of pairs of friends that can be formed by grouping these npeople into exactly mteams.
Examples: 

Input : 5 2 
Output : 4 6 
For maximum no. of pairs, 1st team contains only 1 member and 2nd team contains 4 people which are friends which each other, so no. of pairs in 1st team + no. of pairs in 2nd team = 0 + 6 = total pairs = 6 
For minimum no. of pairs, 1st team contains 2 members and 2nd team contains 3 people which are friends which each other, so no. of pairs in 1st team + no. of pairs in 2nd team = 1 + 3 = total pairs = 4
Input : 2 1 
Output : 1 1

Explanation: 
First of all, we have to put 1 member in each team to satisfy the constraint. So we are left with n-mpeople. 
1. For maximum no. of pairs 
It can be seen that maximum no. pairs can result only by putting all of the remaining members of the same team. It can be explained as follows: 
Consider 2 teams one containing x people and other containing 1 person, now we have to add 1 more person to both the teams, adding him/her to the team of x people increases the no. of pairs by x while adding him to the other team only increases the no. of pairs by 1. Hence, for maximum no. of pairs, we have to put all the remaining people in the same team. 
Now the teams distribution for maximum no. of pairs would be something like this: 
n-m+1, 1, 1, ...
Hence, 

    $$Max. pairs = \frac{(n-m)*(n-m+1)}{2} $$

Ex: If a team consists of 3 persons, the 3rd person has 1 and 2 as friends, the 2nd person has 1 as a friend. Therefore, 2+1 = ((3-1)*(3))/2 friends
2. For minimum no. of pairs 
Now from the same explanation, it can be seen that minimum no. of pairs are obtained when all the persons are distributed equally in the teams. Hence remaining n-m people should be distributed in m teams so that each team contains (n-m)/m more people. Now there are (n-m)\%mpeople still remaining which are to be filled 1 in each team (can be seen contrary to the above condition of maximum). 
Now the team distribution for minimum no. of pairs would be something like this: 
Each team has (n-m)/m + 1members and (n-m)\%mteams have one member extra. 
So total no. of pairs = Total no.s of pairs in m teams each of size ((n-m)/m)+1+ No. of pairs formed by adding 1 person in (n-m)\%mteams which have size ((n-m)/m)+1

    $$ Min. pairs = m*\frac{((n-m)/m+1)*((n-m)/m)}{2} + ceil((n-m)/m)*(n-m)\%m $$

  • Python3
  • Javascript
// CPP program to find minimum and maximum no. of pairs
#include <bits/stdc++.h>
using namespace std;
void MinimumMaximumPairs(int n, int m)
{
int max_pairs = ((n - m + 1) * (n - m)) / 2;
int min_pairs = m * (((n - m) / m + 1) * ((n - m) / m)) / 2 +
ceil((n - m) / double(m)) * ((n - m) % m);
cout << "Minimum no. of pairs = " << min_pairs << "\n";
cout << "Maximum no. of pairs = " << max_pairs << "\n";
}
// Driver code
int main()
{
int n = 5, m = 2;
MinimumMaximumPairs(n, m);
return 0;
}

Output 

Minimum no. of pairs =  4
Maximum no. of pairs =  6

Time Complexity: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK