Quorum
SRM 687 · 2016-04-01 · by lg5293
Problem Statement
In one organization they have n different committees. The organization has a very large number of employees. Each employee is a member of each committee.
Each committee has a quorum: the smallest number of members that have to be present to have an official meeting.
You are given a
You are also given an
Notes
- The value of n is not given explicitly. Instead, you can determine it as the number of elements in arr.
Constraints
- arr will contain between 1 and 50 elements, inclusive.
- Each element of arr will be between 1 and 50.
- k will be between 1 and the number of elements of arr, inclusive.
{5,2,3}
1
Returns: 2
There are three committees. The first committee requires 5 members to start a meeting, the second requires 2, and the third requires 3 members. As k=1, there was one meeting yesterday. The smallest possible solution is that it was a meeting of the second committee and that exactly 2 employees attended that meeting.
{1,1,1,1,1}
5
Returns: 5
All five committees had a meeting yesterday. We need at least one person per meeting. No person can attend more than one meeting. Hence, there must have been at least 5 different people.
{50,2,9,49,38}
3
Returns: 49
{20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}
14
Returns: 105
{29,12,24,43,12,34,49,3,16,26,32,14,27,35,25,34,9,11,8,19,8,44,17,15,26,30,3,41,22,36,26,1,10,4,23,34,50,6,33}
38
Returns: 841
Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Quorum with a public method int count(vector<int> arr, int k) · 38 test cases · 2 s / 256 MB per case