Statistics

Problem Statement for "Quorum"

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 int[] arr with n elements. Each element of arr is the quorum of one committee.

You are also given an int k. Yesterday, k different committees had an official meeting, all at the same time. Obviously, each person attended at most one of those meetings. Compute and return the smallest possible number of people who attended a meeting yesterday.

Definition

Class:
Quorum
Method:
count
Parameters:
int[], int
Returns:
int
Method signature:
int count(int[] arr, int k)
(be sure your method is public)

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.

Examples

  1. {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.

  2. {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.

  3. {50,2,9,49,38}

    3

    Returns: 49

  4. {20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}

    14

    Returns: 105

  5. {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

  6. {8,14,33,34,8,9,1,43,34,14,18,23,12,29,8,42,42,28,34,10,6,24,39,17,13,22,44,44,3,22,38,36,1,34,36,50,7,27,16,4,32}

    38

    Returns: 821

  7. {29,6,46,12}

    1

    Returns: 6

  8. {45,20,16}

    1

    Returns: 16

  9. {39,47,36,50,36,25,16,5,20,27,19,41,2,25,21,20,16}

    8

    Returns: 119

  10. {44,41,15,19,22}

    1

    Returns: 15

  11. {35,18,27,18,27,15,24,9,24,27,5,6,5,9,39,18,1,30,37,11,34,25,20,39,17,18,1}

    20

    Returns: 298

  12. {50,33,31,14,43,28,25,39,27,9,47,6,16,46,17,37,41,23,11,19,32,41,39,36,42,42,47,29,34,43,39,5,42,12,42,48,44,37,32}

    8

    Returns: 90

  13. {2,29,16,2,49,44,8,17,44,41,13,18,14,14,23,2,30,49,32,42,50,45,21,33,20,20,7,18,36,50,32,21,30,33,11,1,23,5,8}

    10

    Returns: 59

  14. {36,28,47,24,43,14,21,20,5,14,13,32,30,27,4,35,10,40,16,36,48,44,29,41,14,36}

    16

    Returns: 301

  15. {2,1,20}

    1

    Returns: 1

  16. {29,12,9,23,19,7,28,30,26,30,49,38,18,15,20,41,12,38,5,36,31,42,41,4,44,33,36}

    12

    Returns: 170

  17. {3,23,41,21,37,21,10,47,36,27,9,35,44,11,3,38,16,25,6,7,41,20,30,22,31,15,42,29,8,25,44,35,39,25,38,3,41,38,12,43,22}

    28

    Returns: 530

  18. {9,10,13,24,33,24,12,42,3,26,22,25,34,39,45,31,13,12,28,18,24,42,17,39,26,24,39,12,43,6,33}

    1

    Returns: 3

  19. {13,39,37,29,47,14,37,32,2,42,50,19,26,37,34,12}

    11

    Returns: 255

  20. {18,4,26,6,24,16,26,41,4,26,42,19,2,32,19,12,37,5,49,46,4,7,4,6}

    1

    Returns: 2

  21. {3,13}

    2

    Returns: 16

  22. {38,36,30,46,45,10,4,43,33,48}

    2

    Returns: 14

  23. {5,18,4,42,42,33,32,26,40,5,46,34,30,3,9,33,43,33,28,6,43,34,48,25,11,10,20,14,36,47,8,2,4,3,42,26}

    3

    Returns: 8

  24. {18,7,29,41,39,41,43,29,26,6,23,42,23,23,30,2,26,47,12,43,18}

    7

    Returns: 86

  25. {26,45,32,6,39,23,32,8,26,26,37,49,20,12,22,26,48,26,35,45,39}

    3

    Returns: 26

  26. {34,43,22,32,45,3,3,13,30,3,35,14,34,14,30,4,23,38,48,21,41,30,29,35,35,28,22,15,39,33}

    19

    Returns: 369

  27. {8,14,39,22,24,8,27,20,17,15,16}

    4

    Returns: 45

  28. {37,50,50,20,28,35,11,21,35,5,46,5,8,3,37,4,21,50,32}

    13

    Returns: 228

  29. {36,9,49,40,7,46,50,26,20,28,13,26,17,26,31,19,20,39,9,45,4,46}

    22

    Returns: 606

  30. {32,8,29,32,10,44,12,31,44,43,7,17,44,33,39,37,31,20,30,44,11,38,42,48,33,3,23,9,36,38,48,33,48,10,29,1,27,11,22,30,37,18,16,17,32,12,26,23,9,7}

    39

    Returns: 842

  31. {27,45,17,26,50,22,45,32,16,38,4,28,32,12,31,4,10,2,20,6,7,29,38,36,16,5,35,39,12,41,39,32,40,45,32,35,18,10,25,15,7,17,49,6,38,5,39,43,34,43}

    22

    Returns: 256

  32. {35,20,18,12,5,24,10,18,45,6,12,22,11,31,17,26,47,4,50,37,42,14,9,2,25,50,6,43,37,22,27,49,35,2,9,5,7,36,29,37,32,41,25,24,4,1,35,13,35,23}

    41

    Returns: 765

  33. {24,32,50,48,7,4,26,28,3,29,2,1,16,40,37,22,31,22,26,46,19,47,25,1,22,1,36,31,43,6,39,44,35,21,2,47,45,8,29,42,18,14,38,28,23,24,49,37,23,22}

    38

    Returns: 773

  34. {25,5,41,4,10,12,50,39,41,30,12,35,19,11,48,47,19,16,43,50,40,35,19,44,4,35,23,3,24,21,29,25,34,14,37,21,32,33,43,5,50,30,5,17,16,42,16,44,34,10}

    4

    Returns: 16

  35. {1, 1 }

    2

    Returns: 2

  36. {5, 6, 7, 8 }

    4

    Returns: 26

  37. {50, 2, 9, 49, 38 }

    3

    Returns: 49

  38. {1, 2, 3, 4 }

    4

    Returns: 10

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: