Statistics

Problem Statement for "ShoppingSurveyDiv2"

Problem Statement

A store sells M different items, conveniently numbered 0 through M-1. For a shopping survey you interviewed N customers. Each customer responded to the survey with a list of items they've bought. Each customer bought at most one of each item. It is possible that some customers did not buy anything at all.

After collecting the responses, you've summed up the results and found that s[i] people have bought item i. Due to an unfortunate accident, you've then lost the actual survey responses. All you have left are the values s[i] you computed.

You are now supposed to report the number of big shoppers among the survey respondents. A big shopper is defined as a customer who has bought all M items. Of course, having lost the detailed responses, you might be unable to determine the actual number of big shoppers.

You are given the int N and the int[] s with M elements. Compute and return the smallest possible number of big shoppers.

Definition

Class:
ShoppingSurveyDiv2
Method:
minValue
Parameters:
int, int[]
Returns:
int
Method signature:
int minValue(int N, int[] s)
(be sure your method is public)

Constraints

  • N will be between 1 and 100, inclusive.
  • s will contain between 1 and 100 elements, inclusive.
  • Each element in s will be between 0 and N, inclusive.

Examples

  1. 5

    {3, 3}

    Returns: 1

    There are 5 customers and 2 items in the store. Each of the items was bought by three of the customers. Since there are five people and a total of six bought items, we must have at least one big shopper. And we can easily verify that there could have been exactly one big shopper and four other customers who have bought one item each.

  2. 100

    {97}

    Returns: 97

  3. 10

    {9, 9, 9, 9, 9}

    Returns: 5

  4. 7

    {1, 2, 3}

    Returns: 0

  5. 5

    {3, 3, 3}

    Returns: 0

  6. 100

    {100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}

    Returns: 100

  7. 92

    {92,90,92,92,92,89,92,91,92,89,92}

    Returns: 83

  8. 99

    {99,99,99,99,99,96,99,99,99,99,98,99,99}

    Returns: 95

  9. 64

    {64,61,64,61,64,64,64,64,61,64,63,64,64,61}

    Returns: 51

  10. 50

    {50,50,50,49,50,50,50,47,50,50,50}

    Returns: 46

  11. 64

    {62,64,64,61,64,64,62,64,64,64,63,64}

    Returns: 56

  12. 100

    {100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,0,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}

    Returns: 0

  13. 58

    {58,58,58,56,58,58,58,58,58,58,50,58,58,58,58,58,58,58,58,58,51,58,58,58,58,58,58,58,58,58,58,58,56,58,58,58,58,58,56,58,58,58,57,58,58,58,58,58,51,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58}

    Returns: 29

  14. 55

    {55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,50,55,55,55,55,55,55,55,55,55,50,55,55,55,55,55,55,55,55,55,55,55,54,46,55,55,47,55,55,55,50,55,55,55,49,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55}

    Returns: 16

  15. 83

    {82,83,83,83,83,83,83,83,83,83,83,83,83,76,83,83,83,83,83,83,83,83,83,83,83,83,74,83,75,83,83,83,83,83,83,83,83,83,83,78,83,83,83,83,83,74,83,83,83,83,83,83,83,83,83,83,83,83,83,83,83,83,83,83,78,83,83,78,83,83,74,83,83,83,83,83,83,83,83,83,83,83,83,83,83}

    Returns: 25

  16. 55

    {55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,55,53,55,55,55,55,50,55,55,55,55,55,48,54,55,55,55,55,55,47,55,48,55,55,50,55,50,55,55,55,55,55,55,55,55,48,55,55,55,55}

    Returns: 8

  17. 52

    {46,52,52,48,52,52,52,52,52,47,52,48,52,52,52,52,52,52,52,52,52,47,52,52,52,44,52,52,52,52,52,52,52,52,52,52,52,52,52,52,52,52,52,52,52,52,52,52,52,44,52,52,52,52,52,52,52,52,52,52,52,52,52,48,52,52,52,52,52,52,52,52,52,52,52,52,45,52,52,45,52,52,52,52,50,52,52,52,52,52,47,52,52,52}

    Returns: 0

  18. 89

    {89,86,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,71,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,71,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,89,84}

    Returns: 45

  19. 86

    {86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,75,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,86,78,86,86,86,86,86,86,86,86,86,86,86}

    Returns: 67

  20. 92

    {92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,77,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,92,91,92,92,92}

    Returns: 76

  21. 93

    {83,81,93,81,80,88,84,92,81}

    Returns: 19

  22. 92

    {89,84,83,90,81,82,91,91}

    Returns: 47

  23. 75

    {75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75,75}

    Returns: 75

  24. 40

    {40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40}

    Returns: 40

  25. 11

    {7,1,11,4,5,9,11,6,3,2,8,2,6,8,7,0,6,5,3,9,3,7,2,11,10,1,4,11,11,2,3}

    Returns: 0

  26. 46

    {40,46,43,19,40,21,9,30,18,16,21,28,44,23,23,2,19,34,17,14,8,18,13,31,14,42,27,8,32,16,22,42,0,16,6,39,25,37,36,39,15,20,42,28,46,25,37,33,9,14}

    Returns: 0

  27. 11

    {3,11,0,6,7,7,7,9,3,6,4,1,0,4,11,10,6,10,7,10,2,8,1,7,10,7,7,10,8,3,3,11,10,9,2,2,8,7,5,1,0,7,2,3,7,6,1,3,7,1,1,6,0,5,5,4,6,1,5,10,2,1,11,2,1,11,0,8,2,10,9,3,7,9,9,4,7,4,6,10,6,4,7,8,9,2,3,4,3,6}

    Returns: 0

  28. 25

    {24,24,25,24,25,24,24,25,24,24,24,24,25,25,24,25,24,25,24,24,24,25,25,24,25,24,25,25,25,24,25,25,25,24,25}

    Returns: 7

  29. 25

    {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

    Returns: 0

  30. 49

    {31,33,41,45,42,0,49,29,42,48,25,36,44,41,36,30,33,35,49,34,36,49,38,44,37,37,31,41,49,38,45,42,29,29,41,40,36,42,29,44,29,32,29,25,28,24,27,26,47,48,27,47,29,33,42,44,31,40,35,40,30,43,46,45,44,30,39,45,41,29,34,40,49,34,44,33,38,30,43,25,26,39,27}

    Returns: 0

  31. 45

    {26,23,34,34,42,37,34,31,45,23,42,41,33,45,45,37,37,38,43,32,31,43,41,22,39,33,25,30,35,31,36,22,39,22,36,34,44,38,34,22,36,44,42,0,43,29,25}

    Returns: 0

  32. 100

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    Returns: 0

  33. 3

    {3, 3, 3, 3 }

    Returns: 3

  34. 100

    {70, 75, 80, 85 }

    Returns: 10

  35. 3

    {1, 1, 1 }

    Returns: 0

  36. 2

    {2, 2 }

    Returns: 2

  37. 3

    {3, 3 }

    Returns: 3

  38. 5

    {3, 3, 3, 3 }

    Returns: 0

  39. 5

    {1, 1 }

    Returns: 0

  40. 5

    {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    Returns: 5

  41. 5

    {3, 3, 3 }

    Returns: 0

  42. 4

    {1, 1, 1, 1, 1 }

    Returns: 0

  43. 100

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }

    Returns: 100

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: