Statistics

Problem Statement for "FixedSizeSums"

Problem Statement

You are given two positive integers, sum and count. Consider all possible ways to express sum as a sum of exactly count positive integers. Two ways are considered equal if we can obtain one from the other by changing the order of the summed numbers. For example, 8=3+2+1+1+1 is the same as 8=1+3+1+2+1, but not the same as 8=3+2+2+1. Thus we will only be interested in such summations where the summed integers are in non-increasing order.

For example, if sum=8 and count=3, the possible ways are: 

8 = 6+1+1
8 = 3+3+2
8 = 4+2+2
8 = 4+3+1
8 = 5+2+1

We may now order these summations in the following way: Order them according to the first summand in decreasing order. In case of a tie, order them according to the second summand, etc. In general, to compare two summations, look at the first summand where they differ. The one where this summand is larger will be earlier in our order.

For our previous example, the correct order is: 

8 = 6+1+1
8 = 5+2+1
8 = 4+3+1
8 = 4+2+2
8 = 3+3+2

You will be given three ints: sum, count and index, where index contains a zero-based index of a summation in the order defined above. Your method should return a String containing that summation in the form "SUM=SUMMAND(1)+...+SUMMAND(count)". If index is too large to specify a valid summation, return an empty string.

Definition

Class:
FixedSizeSums
Method:
kthElement
Parameters:
int, int, int
Returns:
String
Method signature:
String kthElement(int sum, int count, int index)
(be sure your method is public)

Notes

  • You may assume that the total number of possible summations will never exceed 2,000,000,000.

Constraints

  • sum is between 1 and 150, inclusive.
  • count is between 1 and 150, inclusive.
  • index is between 0 and 2,000,000,000, inclusive.

Examples

  1. 8

    3

    2

    Returns: "8=4+3+1"

    This is the example from the problem statement. Look at the ordered list of possible summations and number them starting with zero.

  2. 13

    1

    0

    Returns: "13=13"

    There is only one possibility here.

  3. 13

    13

    0

    Returns: "13=1+1+1+1+1+1+1+1+1+1+1+1+1"

    Again, there is only one possible summation.

  4. 7

    10

    3

    Returns: ""

    This is impossible. A sum of 10 positive integers is never equal to 7.

  5. 17

    2

    4

    Returns: "17=12+5"

    The first five possible summations are: "17=16+1", "17=15+2", "17=14+3", "17=13+4", and "17=12+5".

  6. 140

    17

    87654321

    Returns: "140=40+31+15+15+9+7+4+4+2+2+2+2+2+2+1+1+1"

  7. 150

    23

    1901740433

    Returns: "150=7+7+7+7+7+7+7+7+7+7+7+7+6+6+6+6+6+6+6+6+6+6+6"

  8. 150

    23

    1903000047

    Returns: ""

  9. 150

    22

    1901740430

    Returns: ""

  10. 150

    24

    1765432109

    Returns: "150=17+17+16+14+12+12+11+9+9+7+7+2+2+2+2+2+2+1+1+1+1+1+1+1"

  11. 148

    40

    470000000

    Returns: ""

  12. 1

    1

    0

    Returns: "1=1"

  13. 1

    1

    1

    Returns: ""

  14. 1

    1

    2

    Returns: ""

  15. 1

    1

    3

    Returns: ""

  16. 1

    2

    0

    Returns: ""

  17. 1

    2

    1

    Returns: ""

  18. 1

    2

    2

    Returns: ""

  19. 1

    2

    3

    Returns: ""

  20. 1

    3

    0

    Returns: ""

  21. 1

    3

    1

    Returns: ""

  22. 1

    3

    2

    Returns: ""

  23. 1

    3

    3

    Returns: ""

  24. 1

    4

    0

    Returns: ""

  25. 1

    4

    1

    Returns: ""

  26. 1

    4

    2

    Returns: ""

  27. 1

    4

    3

    Returns: ""

  28. 2

    1

    0

    Returns: "2=2"

  29. 2

    1

    1

    Returns: ""

  30. 2

    1

    2

    Returns: ""

  31. 2

    1

    3

    Returns: ""

  32. 2

    2

    0

    Returns: "2=1+1"

  33. 2

    2

    1

    Returns: ""

  34. 2

    2

    2

    Returns: ""

  35. 2

    2

    3

    Returns: ""

  36. 2

    3

    0

    Returns: ""

  37. 2

    3

    1

    Returns: ""

  38. 2

    3

    2

    Returns: ""

  39. 2

    3

    3

    Returns: ""

  40. 2

    4

    0

    Returns: ""

  41. 2

    4

    1

    Returns: ""

  42. 2

    4

    2

    Returns: ""

  43. 2

    4

    3

    Returns: ""

  44. 3

    1

    0

    Returns: "3=3"

  45. 3

    1

    1

    Returns: ""

  46. 3

    1

    2

    Returns: ""

  47. 3

    1

    3

    Returns: ""

  48. 3

    2

    0

    Returns: "3=2+1"

  49. 3

    2

    1

    Returns: ""

  50. 3

    2

    2

    Returns: ""

  51. 3

    2

    3

    Returns: ""

  52. 3

    3

    0

    Returns: "3=1+1+1"

  53. 3

    3

    1

    Returns: ""

  54. 3

    3

    2

    Returns: ""

  55. 3

    3

    3

    Returns: ""

  56. 3

    4

    0

    Returns: ""

  57. 3

    4

    1

    Returns: ""

  58. 3

    4

    2

    Returns: ""

  59. 3

    4

    3

    Returns: ""

  60. 4

    1

    0

    Returns: "4=4"

  61. 4

    1

    1

    Returns: ""

  62. 4

    1

    2

    Returns: ""

  63. 4

    1

    3

    Returns: ""

  64. 4

    2

    0

    Returns: "4=3+1"

  65. 4

    2

    1

    Returns: "4=2+2"

  66. 4

    2

    2

    Returns: ""

  67. 4

    2

    3

    Returns: ""

  68. 4

    3

    0

    Returns: "4=2+1+1"

  69. 4

    3

    1

    Returns: ""

  70. 4

    3

    2

    Returns: ""

  71. 4

    3

    3

    Returns: ""

  72. 4

    4

    0

    Returns: "4=1+1+1+1"

  73. 4

    4

    1

    Returns: ""

  74. 4

    4

    2

    Returns: ""

  75. 4

    4

    3

    Returns: ""

  76. 147

    1

    0

    Returns: "147=147"

  77. 147

    1

    1

    Returns: ""

  78. 147

    1

    2000000000

    Returns: ""

  79. 143

    143

    0

    Returns: "143=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  80. 143

    143

    1

    Returns: ""

  81. 143

    142

    0

    Returns: "143=2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  82. 143

    142

    1

    Returns: ""

  83. 143

    141

    0

    Returns: "143=3+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  84. 143

    141

    1

    Returns: "143=2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  85. 143

    141

    2

    Returns: ""

  86. 73

    16

    123456

    Returns: "73=20+7+6+6+6+5+5+4+3+3+3+1+1+1+1+1"

  87. 150

    23

    12

    Returns: "150=123+6+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  88. 150

    23

    123

    Returns: "150=118+5+3+2+2+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  89. 150

    12

    1234

    Returns: "150=121+10+10+1+1+1+1+1+1+1+1+1"

  90. 150

    23

    12345

    Returns: "150=101+13+5+5+5+2+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  91. 150

    24

    123456

    Returns: "150=89+17+9+4+2+2+2+2+2+2+2+2+2+2+2+1+1+1+1+1+1+1+1+1"

  92. 150

    23

    1234567

    Returns: "150=77+28+9+8+6+4+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  93. 50

    150

    987654321

    Returns: ""

  94. 150

    150

    987654321

    Returns: ""

  95. 150

    23

    87654321

    Returns: "150=48+27+13+13+7+4+4+4+4+3+3+3+3+3+2+2+1+1+1+1+1+1+1"

  96. 150

    25

    234567890

    Returns: "150=39+23+12+10+6+5+5+4+4+4+4+4+4+4+4+4+3+3+2+1+1+1+1+1+1"

  97. 113

    17

    643523

    Returns: "113=49+24+5+4+4+4+4+4+3+3+3+1+1+1+1+1+1"

  98. 113

    65

    3253265

    Returns: ""

  99. 147

    2

    35

    Returns: "147=111+36"

  100. 140

    17

    87654321

    Returns: "140=40+31+15+15+9+7+4+4+2+2+2+2+2+2+1+1+1"

  101. 150

    25

    2000000000

    Returns: ""

  102. 150

    20

    1003

    Returns: "150=114+9+4+3+3+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1"

  103. 147

    37

    123456789

    Returns: "147=30+20+15+15+11+6+6+4+4+4+3+2+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  104. 141

    13

    87653321

    Returns: "141=37+21+17+16+15+10+7+5+4+4+2+2+1"

  105. 150

    77

    1089

    Returns: "150=57+7+3+3+3+2+2+2+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  106. 150

    50

    10000

    Returns: "150=75+11+9+7+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  107. 150

    50

    1000000

    Returns: "150=52+14+10+8+5+4+3+2+2+2+2+2+2+2+2+2+2+2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1"

  108. 141

    13

    87653021

    Returns: "141=37+21+17+16+15+12+5+3+3+3+3+3+3"

  109. 150

    17

    90000000

    Returns: "150=50+27+14+13+5+5+5+5+5+5+4+2+2+2+2+2+2"

  110. 150

    150

    2000000000

    Returns: ""

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: