Statistics

Problem Statement for "CoinConstruction"

Problem Statement

This task is about a bag of coins. Each coin in the bag has a positive integer value. The values are not necessarily distinct. A positive integer X is called good if there is a nonempty subset of coins such that their total value is exactly X. We will use S to denote the set of all good integers.

Here are some examples:
  • If the bag contains coins with values 3, 4, 7, the set S will be {3, 4, 7, 10, 11, 14}.
  • If the bag contains coins with values 2, 2, 10, the set S will be {2, 4, 10, 12, 14}.
You are given an int k. Construct a bag of coins with the following properties:
  • The set S of good integers has exactly k elements.
  • The bag must contain between 1 and 20 coins, inclusive.
  • The value of each coin must be between 1 and 10^9, inclusive.
Note that your bag may contain multiple coins with the same value. We guarantee that for the constraints used in this task there is always a solution. If there are multiple solutions, you may choose any one of them.

Return a int[] containing the values of the coins in your bag.

Definition

Class:
CoinConstruction
Method:
construct
Parameters:
int
Returns:
int[]
Method signature:
int[] construct(int k)
(be sure your method is public)

Constraints

  • k will be between 1 and 1,000,000, inclusive.

Examples

  1. 6

    Returns: {3, 4, 7 }

    This is the case mentioned in the statement: S = {3, 4, 7, 10, 11, 14}.

  2. 26

    Returns: {1, 1, 10, 10, 100, 100 }

    This time S contains all values of the form (a * 100 + b * 10 + c) where a, b, c are in {0, 1, 2}, except for a = b = c = 0.

  3. 7

    Returns: {1, 1, 1, 1, 1, 1, 1 }

  4. 1

    Returns: {999999999 }

  5. 1023

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512 }

  6. 1025

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 2 }

  7. 1000000

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475713 }

  8. 999999

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475712 }

  9. 123456

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 57921 }

  10. 654321

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 130034 }

  11. 742

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 231 }

  12. 4072

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2025 }

  13. 384110

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 121967 }

  14. 9

    Returns: {1, 2, 4, 2 }

  15. 494

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 239 }

  16. 572873

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 48586 }

  17. 606618

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 82331 }

  18. 1113

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 90 }

  19. 74745

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 9210 }

  20. 3409

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 1362 }

  21. 12112

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 3921 }

  22. 196292

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 65221 }

  23. 55

    Returns: {1, 2, 4, 8, 16, 24 }

  24. 15164

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 6973 }

  25. 263

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 8 }

  26. 43

    Returns: {1, 2, 4, 8, 16, 12 }

  27. 8483

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 292 }

  28. 60

    Returns: {1, 2, 4, 8, 16, 29 }

  29. 47

    Returns: {1, 2, 4, 8, 16, 16 }

  30. 606

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 95 }

  31. 731836

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 207549 }

  32. 24898

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 8515 }

  33. 1464

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 441 }

  34. 19

    Returns: {1, 2, 4, 8, 4 }

  35. 6

    Returns: {3, 4, 7 }

  36. 7

    Returns: {1, 1, 1, 1, 1, 1, 1 }

  37. 2

    Returns: {1, 1 }

  38. 7

    Returns: {1, 1, 1, 1, 1, 1, 1 }

  39. 18

    Returns: {1, 2, 4, 8, 3 }

  40. 94489

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 28954 }

  41. 1

    Returns: {999999999 }

  42. 2

    Returns: {1, 1 }

  43. 3

    Returns: {1, 2 }

  44. 4

    Returns: {1, 2, 1 }

  45. 5

    Returns: {1, 2, 2 }

  46. 6

    Returns: {3, 4, 7 }

  47. 7

    Returns: {1, 1, 1, 1, 1, 1, 1 }

  48. 8

    Returns: {1, 2, 4, 1 }

  49. 9

    Returns: {1, 2, 4, 2 }

  50. 10

    Returns: {1, 2, 4, 3 }

  51. 11

    Returns: {1, 2, 4, 4 }

  52. 12

    Returns: {1, 2, 4, 5 }

  53. 13

    Returns: {1, 2, 4, 6 }

  54. 14

    Returns: {1, 2, 4, 7 }

  55. 15

    Returns: {1, 2, 4, 8 }

  56. 16

    Returns: {1, 2, 4, 8, 1 }

  57. 17

    Returns: {1, 2, 4, 8, 2 }

  58. 18

    Returns: {1, 2, 4, 8, 3 }

  59. 19

    Returns: {1, 2, 4, 8, 4 }

  60. 20

    Returns: {1, 2, 4, 8, 5 }

  61. 21

    Returns: {1, 2, 4, 8, 6 }

  62. 22

    Returns: {1, 2, 4, 8, 7 }

  63. 23

    Returns: {1, 2, 4, 8, 8 }

  64. 24

    Returns: {1, 2, 4, 8, 9 }

  65. 25

    Returns: {1, 2, 4, 8, 10 }

  66. 26

    Returns: {1, 1, 10, 10, 100, 100 }

  67. 27

    Returns: {1, 2, 4, 8, 12 }

  68. 28

    Returns: {1, 2, 4, 8, 13 }

  69. 29

    Returns: {1, 2, 4, 8, 14 }

  70. 30

    Returns: {1, 2, 4, 8, 15 }

  71. 1000000

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475713 }

  72. 999999

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475712 }

  73. 999998

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475711 }

  74. 999997

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475710 }

  75. 999996

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475709 }

  76. 999995

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475708 }

  77. 999994

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475707 }

  78. 999993

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475706 }

  79. 999992

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475705 }

  80. 999991

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475704 }

  81. 999990

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475703 }

  82. 999989

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475702 }

  83. 999988

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475701 }

  84. 999987

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475700 }

  85. 999986

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475699 }

  86. 999985

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475698 }

  87. 999984

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475697 }

  88. 999983

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475696 }

  89. 999982

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475695 }

  90. 999981

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475694 }

  91. 999980

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475693 }

  92. 999979

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475692 }

  93. 999978

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475691 }

  94. 999977

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475690 }

  95. 999976

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475689 }

  96. 999975

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475688 }

  97. 999974

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475687 }

  98. 999973

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475686 }

  99. 999972

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475685 }

  100. 999971

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 475684 }

  101. 15021

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 6830 }

  102. 1000

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 489 }

  103. 599123

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 74836 }

  104. 500

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 245 }

  105. 50

    Returns: {1, 2, 4, 8, 16, 19 }

  106. 775850

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 251563 }

  107. 524287

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144 }

  108. 100000

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 34465 }

  109. 228228

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 97157 }

  110. 524223

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262080 }

  111. 349525

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 87382 }

  112. 764171

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 239884 }

  113. 3070

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 1023 }

  114. 789987

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 265700 }

  115. 327678

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 65535 }

  116. 78125

    Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 12590 }

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: