Statistics

Problem Statement for "LittleElephantAndBooks"

Problem Statement

Little Elephant from the Zoo of Lviv has a bunch of books. You are given a int[] pages. Each element of pages is the number of pages in one of those books. There are no two books with the same number of pages.

You are also given a int number. As a homework from the teacher, Little Elephant must read exactly number of his books during the summer. (Little Elephant has strictly more than number books.)

All other elephants in the school also got the exact same homework. Little Elephant knows that the other elephants are lazy: they will simply pick the shortest number books, so that they have to read the smallest possible total number of pages. Little Elephant wants to be a good student and read a bit more than the other elephants. He wants to pick the subset of books with the second smallest number of pages. In other words, he wants to pick a subset of books with the following properties:

  • There are exactly number books in the chosen subset.
  • The total number of pages of those books is greater than the smallest possible total number of pages.
  • The total number of pages of those books is as small as possible (given the above conditions).

Return the total number of pages Little Elephant will have to read.

Definition

Class:
LittleElephantAndBooks
Method:
getNumber
Parameters:
int[], int
Returns:
int
Method signature:
int getNumber(int[] pages, int number)
(be sure your method is public)

Constraints

  • pages will contain between 2 and 50 elements, inclusive.
  • Each element of pages will be between 1 and 100, inclusive.
  • There will be no two equal elements in pages.
  • number will be between 1 and N-1, inclusive, where N is the number of elements in pages.

Examples

  1. {1, 2}

    1

    Returns: 2

    There are two books: one with 1 page, the other with 2 pages. As number=1, each of the elephants has to read one book. The lazy elephants will read the 1-page book, so our Little Elephant should read the 2-page one. Thus, the number of pages read by Little Elephant is 2.

  2. {74, 7, 4, 47, 44}

    3

    Returns: 58

    The lazy elephants will read books 1, 2, and 4 (0-based indices). Their total number of pages is 7+4+44 = 55. Little Elephant should pick books 1, 2, and 3, for a total of 7+4+47 = 58 pages. (Note that Little Elephant is allowed to pick any subset, except for the minimal one. In particular, he may read some of the books read by the other elephants.)

  3. {3, 1, 9, 7, 2, 8, 6, 4, 5}

    7

    Returns: 29

  4. {74, 86, 32, 13, 100, 67, 77}

    2

    Returns: 80

  5. {100, 99, 98, 97}

    3

    Returns: 295

  6. {45, 76, 97, 47, 1, 65, 46, 99, 100, 15, 7}

    5

    Returns: 115

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

    16

    Returns: 137

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

    19

    Returns: 191

  9. {68, 35, 1, 70, 25, 79, 59, 63, 65, 6, 46, 82, 28, 62, 92, 96, 43, 37, 5, 3, 54, 93, 83, 22, 17, 19, 48, 27, 72, 39, 13, 100, 36, 95, 4, 12, 23, 34, 74, 42, 69, 45, 58}

    4

    Returns: 14

  10. {24, 42, 30, 79, 17, 36, 91, 43, 89, 7, 41, 65, 49, 47, 6, 71, 51, 2, 94, 85, 55, 57, 67}

    7

    Returns: 127

  11. {9, 45, 40, 27, 24, 38, 39, 19, 83, 30, 42, 34, 16, 59, 5, 31, 78}

    3

    Returns: 33

  12. {87, 22, 46, 25, 73, 71, 30, 78, 74, 98, 13, 91, 62, 37, 56, 68, 75, 32, 53, 51, 42}

    5

    Returns: 127

  13. {31, 8, 42}

    2

    Returns: 50

  14. {58, 88, 54, 84, 46, 10, 59, 22, 89, 23, 47, 7, 31, 14, 69, 1, 92, 63, 56, 11, 60, 25, 38, 49, 96, 42, 3, 51, 37, 75, 21, 97, 100, 85, 82, 35, 19, 39, 28, 68, 29, 94, 8, 18, 15, 17, 36, 52}

    15

    Returns: 217

  15. {20, 57, 99, 4, 25, 9, 45, 10, 90, 3, 96, 86, 94, 44, 24, 88, 15, 49, 1, 59, 19, 81, 97, 82, 58, 73, 23, 39, 93, 80, 91, 92, 16, 89, 12, 35, 56, 29, 47, 63, 87, 76, 34, 70, 43, 17, 52, 22, 100, 77}

    12

    Returns: 149

  16. {76, 13, 1, 11, 4, 70, 62, 89, 2, 90, 56, 24, 3, 86, 83, 27, 18, 58, 33, 55, 22, 77, 30, 69, 93, 26, 35, 50, 42, 46, 61, 19, 54, 40, 80, 97, 88, 38, 67, 94, 96, 98, 17, 87, 6, 15, 72, 64, 14, 9}

    20

    Returns: 332

  17. {14, 57, 22, 59, 47, 83, 82, 45, 97, 23, 30, 62, 36, 51, 74, 67, 60, 93, 40, 54, 25, 55, 11, 46, 50, 87, 75, 69, 19, 88, 6, 92, 3, 26, 78, 15, 35, 73, 34, 71}

    39

    Returns: 1961

  18. {19, 78, 74, 71, 64, 69, 93, 86, 3, 81, 14, 28, 100, 26, 44, 25, 24, 73, 62, 82, 4, 33, 6, 94, 32, 43, 23, 87, 65, 1, 88, 61, 75, 36}

    12

    Returns: 206

  19. {61, 97, 68, 86, 51, 41, 95, 96, 25, 20, 26, 77, 59, 3, 72, 67, 79, 94, 52, 85, 19, 65, 53, 1, 88, 27, 11, 58}

    14

    Returns: 448

  20. {77, 28, 44, 59, 65, 10, 83, 87, 66, 88, 78, 75, 26, 30, 29, 24, 21, 3, 63, 97, 38, 62, 96, 61, 17, 31, 27, 12, 72, 48, 54, 91, 25, 89}

    17

    Returns: 472

  21. {52, 63, 30, 1, 14, 59, 79, 66, 8, 78, 40, 4, 61, 58, 25, 9, 88, 2, 51, 29, 94, 85, 6, 41, 12}

    1

    Returns: 2

  22. {57, 73, 51, 24, 86, 17, 27, 58, 38, 72, 70, 62, 97, 23, 18, 13, 42, 30, 66, 60, 33, 56, 54, 63, 85, 35, 55, 64, 8, 84, 12, 36, 68, 49, 76, 39, 43, 26, 22, 71, 6, 99}

    17

    Returns: 410

  23. {94, 35, 38, 57, 77, 6, 63, 49, 82, 1, 14, 42, 56, 43, 12, 78, 25, 79, 53, 44, 97, 74, 41, 76, 73, 19, 11, 18}

    2

    Returns: 12

  24. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50}

    30

    Returns: 466

  25. {50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 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}

    47

    Returns: 1129

  26. {47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96}

    30

    Returns: 1846

  27. {51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100}

    25

    Returns: 1576

  28. {100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51}

    49

    Returns: 3676

  29. {100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51}

    49

    Returns: 3676

  30. {100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51}

    1

    Returns: 52

  31. {74, 86, 32, 13, 100, 67, 77 }

    2

    Returns: 80

  32. {3, 1, 9, 7, 2, 8, 6, 4, 5 }

    7

    Returns: 29

  33. {1, 20, 21, 22, 23, 24, 25 }

    4

    Returns: 65

  34. {74, 7, 4, 47, 44 }

    3

    Returns: 58

  35. {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 20, 31, 32 }

    12

    Returns: 88

  36. {1, 2, 3, 4 }

    3

    Returns: 7

  37. {1, 2, 3 }

    2

    Returns: 4

  38. {2, 4, 5, 6 }

    2

    Returns: 7

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: