Statistics

Problem Statement for "VectorCostSequence"

Problem Statement

Without consulting your data structures textbook, you have coded up a homemade Vector class. At any point in time the vector has a capacity, the maximum number of values it can hold, and a size, the number of values it currently holds. Typically, adding or removing an element costs 1. If you attempt to add a value to the vector when the size and capacity are equal, the capacity is doubled and then the element is added. This incurs a cost of c+1, where c is the capacity before the insertion. If removing an element makes the size exactly half (no rounding) of the capacity, then the cost is only 1, but the capacity is reduced to the size. Initially, the capacity is 1 and the size is 0. Return the smallest number of additions and removals that will produce the cost d.

Definition

Class:
VectorCostSequence
Method:
getSmallest
Parameters:
int
Returns:
int
Method signature:
int getSmallest(int d)
(be sure your method is public)

Constraints

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

Examples

  1. 1

    Returns: 1

    Performing a single addition gives a cost of 1.

  2. 2

    Returns: 2

    Adding an element and then removing it gives a cost of 2.

  3. 3

    Returns: 2

  4. 4

    Returns: 3

  5. 5

    Returns: 4

  6. 6

    Returns: 3

    We can achieve a cost of 6 with 3 additions. The first costs 1, the second costs 2 and the last costs 3.

  7. 7

    Returns: 4

  8. 8

    Returns: 5

  9. 9

    Returns: 5

  10. 10

    Returns: 5

  11. 11

    Returns: 6

  12. 12

    Returns: 5

  13. 13

    Returns: 6

  14. 14

    Returns: 7

  15. 15

    Returns: 7

  16. 16

    Returns: 7

  17. 478731763

    Returns: 61996

  18. 603642658

    Returns: 69617

  19. 683683401

    Returns: 74501

  20. 319105808

    Returns: 52257

  21. 522943372

    Returns: 64697

  22. 935837931

    Returns: 89891

  23. 591320500

    Returns: 68865

  24. 681515108

    Returns: 74373

  25. 455780540

    Returns: 60589

  26. 712465398

    Returns: 76255

  27. 654406915

    Returns: 72719

  28. 83803505

    Returns: 26622

  29. 830041718

    Returns: 83431

  30. 987230965

    Returns: 93028

  31. 285971001

    Returns: 50226

  32. 579671551

    Returns: 68155

  33. 711561654

    Returns: 76199

  34. 77234324

    Returns: 25821

  35. 99352023

    Returns: 28519

  36. 916746376

    Returns: 88729

  37. 329904996

    Returns: 52909

  38. 848503601

    Returns: 84561

  39. 545542739

    Returns: 66066

  40. 241798170

    Returns: 45903

  41. 168307682

    Returns: 36937

  42. 597676606

    Returns: 69255

  43. 281176951

    Returns: 49935

  44. 975361110

    Returns: 92307

  45. 515358066

    Returns: 64225

  46. 469556446

    Returns: 61435

  47. 641704655

    Returns: 71940

  48. 10817743

    Returns: 9380

  49. 712823038

    Returns: 76279

  50. 101245760

    Returns: 28751

  51. 946835836

    Returns: 90569

  52. 18

    Returns: 7

  53. 24

    Returns: 9

  54. 34

    Returns: 11

  55. 44

    Returns: 13

  56. 50

    Returns: 15

  57. 1000000000

    Returns: 93809

  58. 999999999

    Returns: 93808

  59. 888888888

    Returns: 87023

  60. 876789

    Returns: 2734

  61. 132

    Returns: 29

  62. 999999997

    Returns: 93810

  63. 999876233

    Returns: 93798

  64. 67108870

    Returns: 24571

  65. 50

    Returns: 15

  66. 888888888

    Returns: 87023

  67. 132312412

    Returns: 32539

  68. 278347912

    Returns: 49765

  69. 123456789

    Returns: 31458

  70. 555555555

    Returns: 66683

  71. 1000000000

    Returns: 93809

  72. 54

    Returns: 15

  73. 66617239

    Returns: 24452

  74. 876543291

    Returns: 86268

  75. 100040028

    Returns: 28601

  76. 188990909

    Returns: 39461

  77. 57654576

    Returns: 22269

  78. 975342839

    Returns: 92302

  79. 95522114

    Returns: 28055

  80. 999999999

    Returns: 93808

  81. 999884231

    Returns: 93800

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: