Statistics

Problem Statement for "BinaryCards"

Problem Statement

Karel is a robot. He has a set of 64 cards: for each x between 0 and 63, he has a card that is blank on one side and has 2^x dots on the other side.

Karel's cards are placed on a table. At any moment, the cards show some integer between 0 and (2^64)-1, inclusive. To read the number, you just count all the dots you see.

Karel is using the cards to count from A to B. That is, he is flipping some of the cards in such a way that the numbers A, A+1, ..., B appear in this order.

Of course, Karel is using the shortest possible sequence of flips. Additionally, he always flips the cards one at a time. Sometimes, changing the number from some Z to Z+1 requires Karel to flip more than one card. In that case, he flips the necessary cards ordered by the number of dots they have, starting with the one with the most dots.

For example, if A=6 and B=8, the following will happen:

  • In the beginning, the card with 4 dots and the card with 2 dots are showing the dots, all other cards are blank side up. This shows the number 6.
  • Karel flips the card with 1 dot. Now the number 7 is shown.
  • Karel flips the card with 8 dots.
  • Karel flips the card with 4 dots.
  • Karel flips the card with 2 dots.
  • Karel flips the card with 1 dot. Now the number 8 is shown and Karel is done.

Given are longs A and B. Your method must return the largest number that will be shown at any moment during Karel's counting.

Definition

Class:
BinaryCards
Method:
largestNumber
Parameters:
long, long
Returns:
long
Method signature:
long largestNumber(long A, long B)
(be sure your method is public)

Constraints

  • A will be between 1 and 10^18, inclusive.
  • B will be between A and 10^18, inclusive.

Examples

  1. 6

    6

    Returns: 6

  2. 6

    7

    Returns: 7

  3. 6

    8

    Returns: 15

    This is the example from the problem statement. When flipping cards to create the number 8 from the number 7, Karel starts by flipping the card with 8 dots. At this moment, the number shown on the cards is 15.

  4. 1

    11

    Returns: 15

  5. 35

    38

    Returns: 39

  6. 337007621073450791

    337259621176923563

    Returns: 337769972052787199

  7. 337007621073450791

    363243549783774699

    Returns: 432345564227567615

  8. 337007621073450700

    576460752303429290

    Returns: 1152921504606846975

  9. 13

    999999999999999947

    Returns: 1152921504606846975

  10. 1

    1000000000000000000

    Returns: 1152921504606846975

  11. 1

    1

    Returns: 1

  12. 1000000000000000000

    1000000000000000000

    Returns: 1000000000000000000

  13. 1

    2

    Returns: 3

  14. 1

    3

    Returns: 3

  15. 2

    2

    Returns: 2

  16. 2

    3

    Returns: 3

  17. 3

    3

    Returns: 3

  18. 3

    4

    Returns: 7

  19. 4

    4

    Returns: 4

  20. 13435118322293023

    13435118322293023

    Returns: 13435118322293023

  21. 252967131130464888

    252967131130464888

    Returns: 252967131130464888

  22. 469891784347835618

    469891784347835618

    Returns: 469891784347835618

  23. 258474518727344664

    258474518727344664

    Returns: 258474518727344664

  24. 71857669457162785

    71857669457162785

    Returns: 71857669457162785

  25. 176818103997872891

    176818103997873439

    Returns: 176818103997874175

  26. 673336125333327877

    673336125333328868

    Returns: 673336125333328895

  27. 21184812552106628

    21184812552106728

    Returns: 21184812552106751

  28. 906611261103360176

    906611261103360326

    Returns: 906611261103360511

  29. 631896407723188043

    631896407723188737

    Returns: 631896407723196415

  30. 247024732614360996

    247024732614361943

    Returns: 247024732614426623

  31. 280721490791747993

    280721490791748763

    Returns: 280721490791749631

  32. 461657559838062496

    461657559838062968

    Returns: 461657559838064639

  33. 620089089696830274

    620089089696830603

    Returns: 620089089696831487

  34. 43566986678135226

    43566986678135833

    Returns: 43566986678136831

  35. 528042601210849297

    528042601210849469

    Returns: 528042601210849535

  36. 84536132133068665

    84536132133069319

    Returns: 84536132133076991

  37. 942126680384630477

    942126680384631202

    Returns: 942126680384634879

  38. 829161406158550903

    829161406158551053

    Returns: 829161406158553087

  39. 192864567966073284

    192864567966074101

    Returns: 192864567966074879

  40. 399896204401903756

    399896204401903959

    Returns: 399896204401904127

  41. 655725947309379779

    655725947309380452

    Returns: 655725947309380607

  42. 60991707593202488

    60991707593202638

    Returns: 60991707593202687

  43. 972578212996605153

    972578212996605632

    Returns: 972578212996605951

  44. 104679898968505965

    104679898968506109

    Returns: 104679898968506111

  45. 729958436560262555

    729958436560262795

    Returns: 729958436560263167

  46. 507500148014589508

    507500148014590374

    Returns: 507500148014591999

  47. 91417475999865401

    91417475999865740

    Returns: 91417475999865855

  48. 333840733864662438

    333840733864663435

    Returns: 333840733864665087

  49. 826286096177798903

    826286096177799662

    Returns: 826286096177807359

  50. 592225194635090984

    592225194635091352

    Returns: 592225194635091455

  51. 977759016201489584

    977759016201490202

    Returns: 977759016201490431

  52. 246644132110493584

    246644132110494535

    Returns: 246644132110495743

  53. 439335986138523394

    439335986138524105

    Returns: 439335986138525695

  54. 438788899128495824

    438788899128496339

    Returns: 438788899128500223

  55. 732687986402108031

    836087143253585095

    Returns: 864691128455135231

  56. 92645752026305337

    550113554666774577

    Returns: 576460752303423487

  57. 602049742558610199

    951600406774886073

    Returns: 1152921504606846975

  58. 706337757793877497

    726719184543046995

    Returns: 864691128455135231

  59. 818371022660510048

    980626001687600036

    Returns: 1152921504606846975

  60. 80766787368399593

    370922704980929886

    Returns: 576460752303423487

  61. 414364532474145686

    535084885568801990

    Returns: 576460752303423487

  62. 749924328780360702

    916969508550056468

    Returns: 1152921504606846975

  63. 767103813160910190

    937414842315000059

    Returns: 1152921504606846975

  64. 824229608922636783

    938157792592406450

    Returns: 1152921504606846975

  65. 211914680349424630

    567698046964858784

    Returns: 576460752303423487

  66. 513120303067513709

    799984384704765630

    Returns: 1152921504606846975

  67. 804032651298292590

    986393890336885097

    Returns: 1152921504606846975

  68. 565003508511569449

    651915890827597517

    Returns: 1152921504606846975

  69. 384546583644785051

    928758421871023805

    Returns: 1152921504606846975

  70. 236803334965751562

    530175526899960478

    Returns: 576460752303423487

  71. 959666360481658390

    983713329931865150

    Returns: 1008806316530991103

  72. 973589585442451164

    999944508749318888

    Returns: 1008806316530991103

  73. 342003499769379916

    498421883622934710

    Returns: 576460752303423487

  74. 767693274074903870

    979738263141363679

    Returns: 1152921504606846975

  75. 382513839723571656

    410584681057222251

    Returns: 432345564227567615

  76. 506496661205795359

    541653773009968970

    Returns: 576460752303423487

  77. 318241991786901344

    340649515483168172

    Returns: 360287970189639679

  78. 541827877884334214

    543084169345761379

    Returns: 544935554911830015

  79. 520945445163048875

    521672253894060363

    Returns: 522417556774977535

  80. 337661893084541764

    553806635450033820

    Returns: 576460752303423487

  81. 565112646848659645

    568912171862912374

    Returns: 576460752303423487

  82. 312840585181419594

    314902478955996726

    Returns: 315251973915934719

  83. 365535731318166037

    401109390394047050

    Returns: 432345564227567615

  84. 399447785612834554

    411816984965413976

    Returns: 414331165718085631

  85. 423078048015223971

    533193151865080675

    Returns: 576460752303423487

  86. 291746566948275431

    376667410053414057

    Returns: 432345564227567615

  87. 469070680029655150

    471666199184921483

    Returns: 472877960873902079

  88. 426305944372602670

    482177657795403892

    Returns: 576460752303423487

  89. 345447906666288848

    349191855013225804

    Returns: 351280770934898687

  90. 350037591335932507

    355584378117889903

    Returns: 360287970189639679

  91. 484233815016952022

    485024458018296310

    Returns: 485262859849170943

  92. 329644275178521849

    330818761457996727

    Returns: 331014572611731455

  93. 533986048966540507

    564712102537874406

    Returns: 576460752303423487

  94. 435417121318038471

    435561360106135103

    Returns: 435723263948095487

  95. 381905962783887868

    382181453033419638

    Returns: 382243018373070847

  96. 314290554338338618

    314927847485414766

    Returns: 315251973915934719

  97. 442177711350763352

    442308151667821598

    Returns: 442478663389151231

  98. 390483612063517613

    423352170914714474

    Returns: 432345564227567615

  99. 361239667840171496

    395555987834915904

    Returns: 396316767208603647

  100. 549741646066376252

    550994623595740861

    Returns: 551690954352885759

  101. 333541150425770125

    334168082337383463

    Returns: 334392272332259327

  102. 475673970210278164

    476859012438865115

    Returns: 477381560501272575

  103. 369689640656221229

    413380679774870573

    Returns: 432345564227567615

  104. 545397602878199236

    559459808989470809

    Returns: 576460752303423487

  105. 298971176024131434

    301092822522968189

    Returns: 301741175033823231

  106. 498292963987240092

    503456801495253550

    Returns: 504403158265495551

  107. 314601835217001986

    517160390750787098

    Returns: 576460752303423487

  108. 536116186576008757

    536472320040157462

    Returns: 536491305610510335

  109. 444641271288504247

    493850093000353894

    Returns: 504403158265495551

  110. 1125899906842630

    1125899906842632

    Returns: 1125899906842639

  111. 1

    100000000000000000

    Returns: 144115188075855871

  112. 1

    1125899906842632

    Returns: 2251799813685247

  113. 1

    1000000000000000

    Returns: 1125899906842623

  114. 1

    1099511627776

    Returns: 2199023255551

  115. 1

    1000000230213021

    Returns: 1125899906842623

  116. 237

    834457658766989797

    Returns: 1152921504606846975

  117. 1

    100000000000000

    Returns: 140737488355327

  118. 999999999999999999

    1000000000000000000

    Returns: 1000000000000262143

  119. 1

    1000000000000

    Returns: 1099511627775

  120. 7

    8

    Returns: 15

  121. 1

    37124508045065437

    Returns: 72057594037927935

  122. 1125899906842630

    1688849860263942

    Returns: 2251799813685247

  123. 6419838068042

    6432741199874

    Returns: 6459630813183

  124. 1

    10000000000000000

    Returns: 18014398509481983

  125. 12

    100000000000000000

    Returns: 144115188075855871

  126. 16

    16

    Returns: 16

  127. 11

    13

    Returns: 15

  128. 576460752303423487

    576460752303423488

    Returns: 1152921504606846975

  129. 1

    3475385758524527

    Returns: 4503599627370495

  130. 8

    13

    Returns: 15

  131. 10

    1000000000000008

    Returns: 1125899906842623

  132. 8

    9

    Returns: 9

  133. 1125899906842623

    1125899906842624

    Returns: 2251799813685247

  134. 2147483648

    2394967295

    Returns: 2415919103

  135. 1

    999999999999999999

    Returns: 1152921504606846975

  136. 9876543212345678

    12345678987654321

    Returns: 13510798882111487

  137. 50

    52

    Returns: 55

  138. 128

    147

    Returns: 159

  139. 288230376151711744

    576460752303423488

    Returns: 1152921504606846975

  140. 10

    10

    Returns: 10

  141. 37

    45

    Returns: 47

  142. 149533581377535

    167125767421951

    Returns: 175921860444159

  143. 144115188075855872

    288230376151711744

    Returns: 576460752303423487

  144. 22

    25

    Returns: 31

  145. 71

    73

    Returns: 79

  146. 139480814

    139546340

    Returns: 139591679

  147. 19

    21

    Returns: 23

  148. 1099511627775

    1099511627776

    Returns: 2199023255551

  149. 64

    84

    Returns: 95

  150. 4

    6

    Returns: 7

  151. 35

    36

    Returns: 39

  152. 33

    37

    Returns: 39

  153. 1125899906842624

    1688849860263936

    Returns: 2251799813685247

  154. 234

    34234

    Returns: 65535

  155. 8

    8

    Returns: 8

  156. 19009999990999995

    19909919990909995

    Returns: 20266198323167231

  157. 288230376151711742

    288230376151711743

    Returns: 288230376151711743

  158. 8

    10

    Returns: 11

  159. 576460752504758272

    576601524285743104

    Returns: 576742227280134143

  160. 123456789123456789

    234567892345678900

    Returns: 288230376151711743

  161. 24

    26

    Returns: 27

  162. 2

    13

    Returns: 15

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: