Statistics

Problem Statement for "Byes"

Problem Statement

Recently there was a single-elimination tournament. The tournament consisted of multiple rounds. In each round the players were divided into pairs, each pair played a game, and the loser of each game was eliminated from the tournament. Once there was only a single player left, the tournament terminated and that player was declared its winner.

If the number of players in a round is odd, it is impossible to divide all of them into pairs. Whenever such a situation arised, one of the players was awarded a bye and advanced into the next round without playing a game.

You are given the long lowerBound and the int numberOfByes. You know that the number of players in the tournament was at least lowerBound, and that the total number of byes awarded to players during the tournament was numberOfByes. Determine and return the smallest possible number of players.

Definition

Class:
Byes
Method:
getNumberOfPlayers
Parameters:
long, int
Returns:
long
Method signature:
long getNumberOfPlayers(long lowerBound, int numberOfByes)
(be sure your method is public)

Notes

  • For the constraints given below the answer always exists and fits into a long.

Constraints

  • lowerBound will be between 1 and 2^60, inclusive.
  • numberOfByes will be between 0 and 60, inclusive.

Examples

  1. 3

    1

    Returns: 3

    A tournament with three people looks as follows: In the first round one person gets a bye and the remaining two people play a game. Two people advance from this round. In the second round the two remaining people face off. The loser is out, the winner wins the tournament. As the tournament with three people had exactly one bye, this is what we are looking for.

  2. 4

    1

    Returns: 6

    In a tournament with four players there are no byes. In a tournament with five players there are two byes (one in the first round and one in the second). In a tournament with six players there is a single bye (in the second round), hence six is the correct answer for this test case.

  3. 1234567890123

    0

    Returns: 2199023255552

    Watch out for integer overflow.

  4. 200

    4

    Returns: 202

  5. 127377

    60

    Returns: 1152921504606846977

  6. 23807794064465

    32

    Returns: 23807809028104

  7. 7770125572

    27

    Returns: 7784628228

  8. 139499248824

    3

    Returns: 154618822656

  9. 2

    5

    Returns: 33

  10. 85092

    1

    Returns: 98304

  11. 4

    0

    Returns: 4

  12. 1193

    1

    Returns: 1536

  13. 2229739593591563

    34

    Returns: 2229740861653008

  14. 398384431

    1

    Returns: 402653184

  15. 12

    17

    Returns: 131073

  16. 1

    1

    Returns: 3

  17. 2104491102151437

    53

    Returns: 9007199254740993

  18. 3

    2

    Returns: 5

  19. 39975471133991499

    11

    Returns: 39975494006865920

  20. 4

    5

    Returns: 33

  21. 6

    0

    Returns: 8

  22. 242621803985793

    39

    Returns: 242622702551041

  23. 6447

    4

    Returns: 6464

  24. 1152921504606846976

    30

    Returns: 1152921505680588800

  25. 52926395034013259

    47

    Returns: 52926400952270850

  26. 57350491161509

    55

    Returns: 36028797018963969

  27. 85713743187302

    58

    Returns: 288230376151711745

  28. 3

    1

    Returns: 3

  29. 234

    6

    Returns: 260

  30. 547594739

    46

    Returns: 70368744177665

  31. 213727999450

    41

    Returns: 2199023255553

  32. 1152921504606846976

    42

    Returns: 1152921504607109120

  33. 1031359599

    19

    Returns: 1031372801

  34. 8736258

    18

    Returns: 8736770

  35. 30362032163443231

    37

    Returns: 30362032201007108

  36. 1501762506955302

    31

    Returns: 1501762506956802

  37. 2

    1

    Returns: 3

  38. 12938

    15

    Returns: 32769

  39. 1

    60

    Returns: 1152921504606846977

  40. 1152921504606846976

    36

    Returns: 1152921504623624192

  41. 246

    43

    Returns: 8796093022209

  42. 14823990

    1

    Returns: 15728640

  43. 19608173632

    1

    Returns: 25769803776

  44. 1152921504606846976

    24

    Returns: 1152921573326323712

  45. 104554406420

    0

    Returns: 137438953472

  46. 1

    5

    Returns: 33

  47. 55334008466064143

    18

    Returns: 55334008466079744

  48. 2

    2

    Returns: 5

  49. 4

    1

    Returns: 6

  50. 288

    34

    Returns: 17179869185

  51. 15457231292

    36

    Returns: 68719476737

  52. 2

    60

    Returns: 1152921504606846977

  53. 2507971

    0

    Returns: 4194304

  54. 40807903

    19

    Returns: 40828929

  55. 1152921504606846976

    18

    Returns: 1152925902653358080

  56. 1

    0

    Returns: 1

  57. 3

    5

    Returns: 33

  58. 10405127434097

    8

    Returns: 10405229363200

  59. 3158239170747

    1

    Returns: 3298534883328

  60. 1119929093513635

    35

    Returns: 1119929096994818

  61. 123607717077

    1

    Returns: 128849018880

  62. 21

    55

    Returns: 36028797018963969

  63. 3

    60

    Returns: 1152921504606846977

  64. 2

    44

    Returns: 17592186044417

  65. 257000819

    35

    Returns: 34359738369

  66. 404568667768

    0

    Returns: 549755813888

  67. 3

    0

    Returns: 4

  68. 390160982005

    1

    Returns: 412316860416

  69. 1084267284640593545

    22

    Returns: 1084267284640694272

  70. 5

    13

    Returns: 8193

  71. 3607615

    56

    Returns: 72057594037927937

  72. 858

    42

    Returns: 4398046511105

  73. 14

    9

    Returns: 513

  74. 268678067

    43

    Returns: 8796093022209

  75. 4

    60

    Returns: 1152921504606846977

  76. 94494

    0

    Returns: 131072

  77. 1744200488

    0

    Returns: 2147483648

  78. 71655287405291

    0

    Returns: 140737488355328

  79. 7815141

    57

    Returns: 144115188075855873

  80. 24

    34

    Returns: 17179869185

  81. 114587400

    60

    Returns: 1152921504606846977

  82. 5380883297

    0

    Returns: 8589934592

  83. 956401

    51

    Returns: 2251799813685249

  84. 8427253264770337

    25

    Returns: 8427253264770344

  85. 56300

    0

    Returns: 65536

  86. 858471555

    30

    Returns: 1073741825

  87. 1152921504606846976

    12

    Returns: 1153202979583557632

  88. 5955217264

    1

    Returns: 6442450944

  89. 420843416012567979

    1

    Returns: 432345564227567616

  90. 4718803

    0

    Returns: 8388608

  91. 4

    2

    Returns: 5

  92. 432

    35

    Returns: 34359738369

  93. 1152921504606846976

    6

    Returns: 1170935903116328960

  94. 33064496

    0

    Returns: 33554432

  95. 885316765509372

    1

    Returns: 985162418487296

  96. 550195858414

    0

    Returns: 1099511627776

  97. 75

    56

    Returns: 72057594037927937

  98. 1152921504606846976

    60

    Returns: 1152921504606846977

  99. 1408496021539386

    1

    Returns: 1688849860263936

  100. 197355856008254

    52

    Returns: 4503599627370497

  101. 1021102597816

    25

    Returns: 1021103308804

  102. 81459717906

    52

    Returns: 4503599627370497

  103. 1

    2

    Returns: 5

  104. 1152921504606846976

    54

    Returns: 1152921504606847040

  105. 1037309

    40

    Returns: 1099511627777

  106. 9

    28

    Returns: 268435457

  107. 128654

    1

    Returns: 129024

  108. 1154997088570

    37

    Returns: 1155346202625

  109. 255999072

    1

    Returns: 260046848

  110. 1152921504606846976

    0

    Returns: 1152921504606846976

  111. 307358291143002118

    40

    Returns: 307358291143426049

  112. 276590639

    0

    Returns: 536870912

  113. 361946034577634775

    8

    Returns: 361959227863859200

  114. 13

    39

    Returns: 549755813889

  115. 123498538724723365

    0

    Returns: 144115188075855872

  116. 994961311997321

    6

    Returns: 995058023137280

  117. 1310277910

    0

    Returns: 2147483648

  118. 190

    24

    Returns: 16777217

  119. 2

    21

    Returns: 2097153

  120. 2

    0

    Returns: 2

  121. 1152921504606846976

    48

    Returns: 1152921504606851072

  122. 715261894718

    37

    Returns: 721554505729

  123. 2

    15

    Returns: 32769

  124. 60055185958015

    1

    Returns: 61572651155456

  125. 123456789012345678

    51

    Returns: 123848989752688642

  126. 1238749573485233

    4

    Returns: 1249045209153536

  127. 123456789123456789

    45

    Returns: 123457013857386497

  128. 100000000000000

    1

    Returns: 105553116266496

  129. 5

    0

    Returns: 8

  130. 562949953421312

    30

    Returns: 562949953945600

  131. 1152921504606846976

    10

    Returns: 1154047404513689600

  132. 127

    6

    Returns: 130

  133. 63351

    9

    Returns: 63492

  134. 21

    20

    Returns: 1048577

  135. 31

    2

    Returns: 40

  136. 5

    20

    Returns: 1048577

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: