Statistics

Problem Statement for "EllysCode01"

Problem Statement

Elly came up with an infinite sequence of zeroes and ones. The sequence can be incrementally constructed as follows:
Begin by writing down a zero. Then, repeat the following process forever:
  1. Copy the entire sequence, but change each zero into a one and vice versa.
  2. Append the copy to the current sequence.
The first few iterations of this process look as follows: 0 → 01 → 0110 → 01101001 → 0110100110010110 → 01101001100101101001011001101001 → …
The positions in the sequence are numbered sequentially, starting from zero.

To impress Elly you want to write a program which can quickly answer any question of the following type: "How many ones are in Elly's sequence at positions from L to R, inclusive?"

You are given the longs L and R. Return the total number of ones whose positions lie in the interval [L, R].

Definition

Class:
EllysCode01
Method:
getOnes
Parameters:
long, long
Returns:
long
Method signature:
long getOnes(long L, long R)
(be sure your method is public)

Constraints

  • L and R will be between 0 and 10^18, inclusive.
  • L will be less than or equal to R.

Examples

  1. 5

    15

    Returns: 5

    The interval [5, 15] covers the digits 01101[00110010110]1001011001101001. This subsequence contains 5 ones, so the correct answer is 5.

  2. 101

    185

    Returns: 42

    The answer is 42.

  3. 0

    0

    Returns: 0

    The digit at index zero is 0.

  4. 1

    1

    Returns: 1

    The digit at index one is 1.

  5. 1337

    1337

    Returns: 0

    The digit at 1337-th position is 0.

  6. 12345

    67890

    Returns: 27772

  7. 5192834871235435

    954971273487212547

    Returns: 474889219307988557

  8. 123456789

    987654321

    Returns: 432098766

  9. 12345678910111213

    13121110987654321

    Returns: 387716038771554

  10. 0

    1234567890

    Returns: 617283945

  11. 0

    10101010101010101

    Returns: 5050505050505051

  12. 0

    1000000000000000000

    Returns: 500000000000000000

  13. 1

    1000000000000000000

    Returns: 500000000000000000

  14. 2

    1000000000000000000

    Returns: 499999999999999999

  15. 3

    1000000000000000000

    Returns: 499999999999999998

  16. 4

    1000000000000000000

    Returns: 499999999999999998

  17. 5

    1000000000000000000

    Returns: 499999999999999997

  18. 6

    1000000000000000000

    Returns: 499999999999999997

  19. 7

    1000000000000000000

    Returns: 499999999999999997

  20. 8

    1000000000000000000

    Returns: 499999999999999996

  21. 9

    1000000000000000000

    Returns: 499999999999999995

  22. 42

    1000000000000000000

    Returns: 499999999999999979

  23. 666

    1000000000000000000

    Returns: 499999999999999667

  24. 1337

    1000000000000000000

    Returns: 499999999999999331

  25. 9876543210

    9876543210

    Returns: 1

  26. 9876543211

    9876543211

    Returns: 0

  27. 9876543212

    9876543212

    Returns: 1

  28. 9876543213

    9876543213

    Returns: 0

  29. 9876543214

    9876543214

    Returns: 0

  30. 9876543215

    9876543215

    Returns: 1

  31. 9876543216

    9876543216

    Returns: 0

  32. 9876543217

    9876543217

    Returns: 1

  33. 9876543218

    9876543218

    Returns: 1

  34. 9876543219

    9876543219

    Returns: 0

  35. 100000000000000000

    100000000000000001

    Returns: 1

  36. 100000000000000001

    100000000000000002

    Returns: 2

  37. 100000000000000002

    100000000000000003

    Returns: 1

  38. 100000000000000003

    100000000000000004

    Returns: 1

  39. 100000000000000004

    100000000000000005

    Returns: 1

  40. 100000000000000005

    100000000000000006

    Returns: 0

  41. 100000000000000006

    100000000000000007

    Returns: 1

  42. 100000000000000007

    100000000000000008

    Returns: 2

  43. 100000000000000008

    100000000000000009

    Returns: 1

  44. 111111111111111111

    222222222222222222

    Returns: 55555555555555555

  45. 111111111111111111

    333333333333333333

    Returns: 111111111111111111

  46. 111111111111111111

    444444444444444444

    Returns: 166666666666666666

  47. 111111111111111111

    555555555555555555

    Returns: 222222222222222222

  48. 111111111111111111

    666666666666666666

    Returns: 277777777777777777

  49. 111111111111111111

    777777777777777777

    Returns: 333333333333333333

  50. 111111111111111111

    888888888888888888

    Returns: 388888888888888888

  51. 111111111111111111

    999999999999999999

    Returns: 444444444444444444

  52. 2

    22

    Returns: 11

  53. 4

    60

    Returns: 28

  54. 33

    55

    Returns: 11

  55. 19

    35

    Returns: 9

  56. 15

    72

    Returns: 28

  57. 23

    69

    Returns: 23

  58. 32

    85

    Returns: 27

  59. 75

    97

    Returns: 11

  60. 62

    90

    Returns: 14

  61. 55

    68

    Returns: 7

  62. 38

    52

    Returns: 8

  63. 35

    84

    Returns: 26

  64. 14

    35

    Returns: 11

  65. 10

    71

    Returns: 31

  66. 56

    98

    Returns: 22

  67. 12

    85

    Returns: 37

  68. 96

    99

    Returns: 2

  69. 18

    33

    Returns: 8

  70. 5

    85

    Returns: 40

  71. 54

    75

    Returns: 11

  72. 451890

    867037

    Returns: 207574

  73. 76230

    321707

    Returns: 122739

  74. 23006

    973392

    Returns: 475193

  75. 597330

    937710

    Returns: 170191

  76. 693524

    877441

    Returns: 91959

  77. 351444

    404127

    Returns: 26342

  78. 4990

    796759

    Returns: 395885

  79. 151726

    941793

    Returns: 395034

  80. 507736

    975773

    Returns: 234019

  81. 234304

    369604

    Returns: 67651

  82. 734318

    992420

    Returns: 129052

  83. 656059

    698238

    Returns: 21091

  84. 405953

    957592

    Returns: 275819

  85. 887618

    929194

    Returns: 20789

  86. 251839

    762457

    Returns: 255310

  87. 315642

    516322

    Returns: 100340

  88. 450580

    495228

    Returns: 22324

  89. 102066

    343435

    Returns: 120685

  90. 441144

    524853

    Returns: 41855

  91. 41448

    903698

    Returns: 431126

  92. 6716841653

    6733903110

    Returns: 8530728

  93. 7923936681

    8131428423

    Returns: 103745871

  94. 6071543706

    7175866483

    Returns: 552161389

  95. 2256257840

    4436715194

    Returns: 1090228677

  96. 3037217472

    8870206823

    Returns: 2916494676

  97. 4372915302

    8594768308

    Returns: 2110926504

  98. 3094625887

    9841980128

    Returns: 3373677122

  99. 809256995

    3345182958

    Returns: 1267962982

  100. 1716715741

    9977210091

    Returns: 4130247175

  101. 6535751986

    8303379841

    Returns: 883813928

  102. 714110645

    8143319470

    Returns: 3714604414

  103. 6295268740

    7428933562

    Returns: 566832412

  104. 828576915

    3505065793

    Returns: 1338244440

  105. 256457004

    4196860997

    Returns: 1970201997

  106. 176146776

    8075908043

    Returns: 3949880634

  107. 1182931648

    6009871546

    Returns: 2413469950

  108. 4187506007

    6381789789

    Returns: 1097141892

  109. 2947737076

    9874076386

    Returns: 3463169656

  110. 1629331725

    9970742824

    Returns: 4170705551

  111. 8128322970

    8969288196

    Returns: 420482613

  112. 7787369605059

    39360987953813

    Returns: 15786809174378

  113. 13695111260875

    95310030362241

    Returns: 40807459550683

  114. 63600672172716

    78548068309743

    Returns: 7473698068514

  115. 90492579177590

    97240994539297

    Returns: 3374207680854

  116. 10483371470955

    97770770425231

    Returns: 43643699477139

  117. 34861512857374

    78461173023127

    Returns: 21799830082877

  118. 12300494461742

    36378610049400

    Returns: 12039057793829

  119. 25681678798392

    53317267881347

    Returns: 13817794541478

  120. 27693590018128

    76253554675065

    Returns: 24279982328469

  121. 13678132492915

    92378370503653

    Returns: 39350119005369

  122. 40895753256768

    87419343325065

    Returns: 23261795034149

  123. 2028939142329

    25701979874736

    Returns: 11836520366203

  124. 64045489429859

    92580558508268

    Returns: 14267534539206

  125. 37385076415213

    79773294320019

    Returns: 21194108952403

  126. 38822302751837

    78563015764488

    Returns: 19870356506327

  127. 42210649705397

    79629073110450

    Returns: 18709211702527

  128. 33324907285930

    91871580363689

    Returns: 29273336538880

  129. 5578737234674

    63897383206854

    Returns: 29159322986091

  130. 42929264723150

    83164515490405

    Returns: 20117625383628

  131. 579485013284

    25150343485285

    Returns: 12285429236001

  132. 326861034622559754

    421573677627030276

    Returns: 47356321502235262

  133. 84400971293995011

    259331576759215943

    Returns: 87465302732610467

  134. 463845940912828416

    779855300881004610

    Returns: 158004679984088097

  135. 210589799605312027

    984260243516132275

    Returns: 386835221955410124

  136. 107231421256308937

    687144491399569940

    Returns: 289956535071630503

  137. 173551711086423117

    811285499731939208

    Returns: 318866894322758047

  138. 139880725825605972

    419053614262815064

    Returns: 139586444218604546

  139. 110478423637727797

    291952205449675951

    Returns: 90736890905974078

  140. 364768269648744387

    469414999391978219

    Returns: 52323364871616916

  141. 214502508631763298

    450549923677533756

    Returns: 118023707522885230

  142. 615558842213928697

    714261038354538575

    Returns: 49351098070304940

  143. 559799275165662759

    819123640184841754

    Returns: 129662182509589499

  144. 566854886931660613

    891310522478738273

    Returns: 162227817773538831

  145. 105259452319848079

    441909642659419329

    Returns: 168325095169785626

  146. 247709904124292700

    480947869602487234

    Returns: 116618982739097268

  147. 55133802461636570

    100282036585790303

    Returns: 22574117062076867

  148. 297564370292699716

    810426923131754268

    Returns: 256431276419527276

  149. 152472389910152787

    376171948756359365

    Returns: 111849779423103289

  150. 50580674105394668

    368047066677070119

    Returns: 158733196285837726

  151. 393398358587456117

    582456023421502960

    Returns: 94528832417023422

  152. 10

    1000

    Returns: 495

  153. 16

    17

    Returns: 1

  154. 0

    1

    Returns: 1

  155. 444848094108753

    1729899977544778

    Returns: 642525941718013

  156. 0

    2

    Returns: 2

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: