Statistics

Problem Statement for "KleofasTail"

Problem Statement

Let X be a nonnegative integer. The Kleofas tail of X is an infinite sequence of nonnegative integers, defined as follows:

  • The first element is X.
  • After an even element Y, the next element of the sequence is Y/2.
  • After an odd element Z, the next element of the sequence is Z-1.

For example, the Kleofas tail of 60 starts as follows: 60, 30, 15, 14, 7, 6, ...

You are given longs K, A, and B. Return the number of integers X between A and B, inclusive, such that the Kleofas tail of X contains at least one occurrence of K.

Definition

Class:
KleofasTail
Method:
countGoodSequences
Parameters:
long, long, long
Returns:
long
Method signature:
long countGoodSequences(long K, long A, long B)
(be sure your method is public)

Notes

  • Zero is an even number.

Constraints

  • K will be between 0 and 10^18, inclusive.
  • A will be between 0 and 10^18, inclusive.
  • B will be between 0 and 10^18, inclusive.
  • A will be less than or equal to B.

Examples

  1. 3

    4

    8

    Returns: 2

    The value 3 occurs in the Kleofas tail of 6 and also in the Kleofas tail of 7.

  2. 1

    23457

    123456

    Returns: 100000

    For each X between 23457 and 123456, inclusive, the Kleofas tail of X contains the value 1.

  3. 1234567890123456

    10

    1000000

    Returns: 0

    Each Kleofas tail is a nonincreasing sequence.

  4. 0

    0

    2

    Returns: 3

  5. 7

    123456789012

    123456789034

    Returns: 23

  6. 4

    2

    10

    Returns: 5

  7. 1

    0

    12

    Returns: 12

  8. 0

    0

    1000000000000000000

    Returns: 1000000000000000001

  9. 1

    0

    1000000000000000000

    Returns: 1000000000000000000

  10. 2

    0

    1000000000000000000

    Returns: 999999999999999999

  11. 3

    0

    1000000000000000000

    Returns: 423539247696576512

  12. 4

    0

    1000000000000000000

    Returns: 576460752303423486

  13. 47

    0

    1000000000000000000

    Returns: 36028797018963967

  14. 48

    0

    1000000000000000000

    Returns: 72057594037927934

  15. 96

    0

    1000000000000000000

    Returns: 36028797018963966

  16. 32532534

    43534

    43643643643262

    Returns: 4194302

  17. 435324643263426

    345435

    346436346363263

    Returns: 0

  18. 3253263263267326

    325325256

    3352353263263263

    Returns: 2

  19. 8

    8

    8

    Returns: 1

  20. 8

    9

    9

    Returns: 1

  21. 8

    4376437643743

    5475475475477

    Returns: 1077428964374

  22. 5

    81

    28835084869372468

    Returns: 9007199254740975

  23. 6638512153

    72826464

    823187539409

    Returns: 127

  24. 7

    73077371391

    7656952776382984

    Returns: 1125882726973440

  25. 82653

    28766948

    18147573791

    Returns: 261632

  26. 37701

    658391

    508545755473

    Returns: 16777184

  27. 5545187

    1511801

    262443850

    Returns: 63

  28. 981618

    73

    319841134745304143

    Returns: 1099511627774

  29. 184777099346175

    5

    805

    Returns: 0

  30. 1144372441

    2575157442058

    533555935488665724

    Returns: 536866816

  31. 845473

    87358662

    550604675998880

    Returns: 1073741696

  32. 63108327

    806068143224561

    910750308707474040

    Returns: 17163091968

  33. 7592812

    156058969

    528890271209816

    Returns: 268435392

  34. 8706174

    89497133

    7223040061447801

    Returns: 2147483616

  35. 453229

    912744455

    85371512690174

    Returns: 268433408

  36. 6360073847422

    232896755

    458353355613

    Returns: 0

  37. 26

    3

    2226

    Returns: 254

  38. 9

    4470449

    2427301214

    Returns: 279293279

  39. 25

    638

    49789995431

    Returns: 2147483616

  40. 42

    83125009949634858

    84136392866282652

    Returns: 0

  41. 650

    4395903

    49763674

    Returns: 245760

  42. 32838314

    645475049

    843599986

    Returns: 0

  43. 420052020

    79329904

    7181776464719

    Returns: 65534

  44. 649

    5376633372

    479537200249959803

    Returns: 1125899898454016

  45. 126

    51262

    31598433624305724

    Returns: 562949953420288

  46. 2459852788813

    69465373

    62893420707898749

    Returns: 32767

  47. 14549444143

    643

    2901352713764

    Returns: 255

  48. 66001729947

    747692189

    88330477933

    Returns: 1

  49. 8

    2

    51914222174524950

    Returns: 18014398509481982

  50. 6449339

    482292792

    14557479981

    Returns: 3968

  51. 4672236029067222

    7293

    146528092457229537

    Returns: 62

  52. 88

    2

    72641556994459

    Returns: 2199023255550

  53. 1663

    859085

    9425682

    Returns: 7168

  54. 4696

    496

    741480593331063921

    Returns: 562949953421310

  55. 162065809

    23554932

    856943842958

    Returns: 8191

  56. 154023

    2202945

    714911039

    Returns: 8176

  57. 86938777568910

    6429795

    675074062685506

    Returns: 14

  58. 3626434

    5699994

    379668764

    Returns: 252

  59. 7565

    308705

    19088118364121

    Returns: 4294967232

  60. 4

    617601301555

    57431178689028

    Returns: 34841648694221

  61. 39511

    7439766607003

    80569917140590732

    Returns: 2198754820096

  62. 881

    30043

    829505387314376

    Returns: 1099511627712

  63. 5769561727236040

    7

    216469881014

    Returns: 0

  64. 403532

    612069109660598

    699801554194811

    Returns: 0

  65. 888

    407

    8807399504809482

    Returns: 35184372088830

  66. 353194

    1525839

    675851986478

    Returns: 4194288

  67. 199632

    654339

    6757602337129

    Returns: 134217720

  68. 495

    13946908800

    85058566399875

    Returns: 274844352512

  69. 412184855405306

    421872877046504

    607941353126123

    Returns: 0

  70. 8251

    693596

    1629332107

    Returns: 262016

  71. 208

    232085738

    581424496978461

    Returns: 8796088827904

  72. 2

    3

    3

    Returns: 1

    The Kleofas tail of 3 is 3, 2, 1, 0, 0, 0, ...

  73. 13

    12345

    67890123

    Returns: 8387584

  74. 7

    30

    1000000000000000000

    Returns: 144115188075855866

  75. 1

    0

    10

    Returns: 10

  76. 3534545

    1

    1000000000000000000

    Returns: 549755813887

  77. 6

    48

    99

    Returns: 20

  78. 2

    0

    999999999999999

    Returns: 999999999999998

  79. 2

    1

    100000000000000000

    Returns: 99999999999999999

  80. 2

    1

    4

    Returns: 3

  81. 1

    0

    999999999999999992

    Returns: 999999999999999992

  82. 5

    1

    1000000000000000000

    Returns: 288230376151711743

  83. 3

    1

    1000000000000000000

    Returns: 423539247696576512

  84. 1

    0

    7

    Returns: 7

  85. 1

    0

    123456789101112

    Returns: 123456789101112

  86. 1

    1

    1000000000000000000

    Returns: 1000000000000000000

  87. 10000

    1

    1000000000000000000

    Returns: 281474976710654

  88. 3

    2

    1000000000000000000

    Returns: 423539247696576512

  89. 2

    1

    1000000000000000

    Returns: 999999999999999

  90. 1

    0

    2

    Returns: 2

  91. 2

    1

    10000000000000

    Returns: 9999999999999

  92. 2

    2

    2

    Returns: 1

  93. 1

    0

    0

    Returns: 0

  94. 13

    0

    1000000000000000000

    Returns: 135308871544864768

  95. 1

    0

    1

    Returns: 1

  96. 777

    100

    1000000000000000000

    Returns: 2251799813685247

  97. 0

    1

    1000000000000000000

    Returns: 1000000000000000000

  98. 1

    1

    10000000000

    Returns: 10000000000

  99. 13

    1

    1000000000000000000

    Returns: 135308871544864768

  100. 1352

    123321

    10000000

    Returns: 16128

  101. 1

    1

    999999999999999900

    Returns: 999999999999999900

  102. 1

    1

    100000000000000000

    Returns: 100000000000000000

  103. 24

    1234

    1000000000000

    Returns: 137438953344

  104. 16

    0

    100

    Returns: 14

  105. 2

    1000000000000000000

    1000000000000000000

    Returns: 1

  106. 32

    0

    10000000

    Returns: 1048574

  107. 5328

    1

    1000000000000000000

    Returns: 562949953421310

  108. 822981258385599122

    28316248989464292

    836179613355295595

    Returns: 2

  109. 2

    0

    1

    Returns: 0

  110. 5

    1000000000000000

    1000000000000000

    Returns: 0

  111. 12370

    3085281

    12506503

    Returns: 1536

  112. 1

    0

    100000000000000000

    Returns: 100000000000000000

  113. 1

    0

    3

    Returns: 3

  114. 5

    18

    999999999999999999

    Returns: 288230376151711740

  115. 121

    100000000000000000

    900000000000000000

    Returns: 7881299347898368

  116. 6

    10

    10

    Returns: 0

  117. 2

    1

    3

    Returns: 2

  118. 8

    4

    4

    Returns: 0

  119. 8

    1000

    2000

    Returns: 256

  120. 2

    1

    1

    Returns: 0

  121. 12345

    0

    1000000000000000000

    Returns: 140737488355327

  122. 2

    0

    5

    Returns: 4

  123. 2

    1

    99999999999999999

    Returns: 99999999999999998

  124. 1238

    1

    100000000

    Returns: 262142

  125. 4

    0

    6

    Returns: 2

  126. 6

    1

    1000000000000000000

    Returns: 423539247696576511

  127. 2

    1

    10

    Returns: 9

  128. 0

    1

    2

    Returns: 2

  129. 4

    1

    5

    Returns: 2

  130. 1

    1

    123456789123456789

    Returns: 123456789123456789

  131. 1099511627776

    1

    1000000000000000000

    Returns: 2097150

  132. 2

    0

    13

    Returns: 12

  133. 2

    0

    4

    Returns: 3

  134. 40

    34637

    193431160843

    Returns: 17179867136

  135. 3

    1

    10000000000000

    Returns: 4398046511103

  136. 3

    4

    7

    Returns: 2

  137. 1024

    1

    1

    Returns: 0

  138. 120

    1

    1000000000000000000

    Returns: 18014398509481982

  139. 1000000000000000000

    1000000000000000000

    1000000000000000000

    Returns: 1

  140. 8

    1

    40

    Returns: 14

  141. 10

    1

    10

    Returns: 1

  142. 4

    1

    10

    Returns: 5

  143. 4

    8

    12

    Returns: 4

  144. 1

    1

    1

    Returns: 1

  145. 10

    19

    1353

    Returns: 326

  146. 6

    0

    1000000000000000000

    Returns: 423539247696576511

  147. 2

    0

    0

    Returns: 0

  148. 8

    0

    7

    Returns: 0

  149. 33

    999999999999999999

    1000000000000000000

    Returns: 0

  150. 16

    20

    100

    Returns: 12

  151. 1

    86248

    120591

    Returns: 34344

  152. 26

    15

    1547546

    Returns: 131070

  153. 1

    1

    10

    Returns: 10

  154. 199

    100000000000000000

    1000000000000000000

    Returns: 8444249301319680

  155. 2

    1

    1000000000000000000

    Returns: 999999999999999999

  156. 1

    10

    12

    Returns: 3

  157. 4

    3

    8

    Returns: 3

  158. 12

    123

    12345678

    Returns: 2097120

  159. 100

    100

    100

    Returns: 1

  160. 4

    13

    1000000000000000000

    Returns: 576460752303423480

  161. 1

    100000000000000000

    1000000000000000000

    Returns: 900000000000000001

  162. 14

    14

    103

    Returns: 14

  163. 30136

    17078

    49762

    Returns: 2

  164. 8

    7

    20

    Returns: 6

  165. 203

    18

    1182

    Returns: 7

  166. 2012

    10000000000000000

    1000000000000000000

    Returns: 1108307720798208

  167. 123456

    678910

    123456789

    Returns: 2032

  168. 1

    0

    18

    Returns: 18

  169. 1

    0

    6

    Returns: 6

  170. 4

    1

    1000000000000000000

    Returns: 576460752303423486

  171. 40

    0

    45

    Returns: 2

  172. 100000000000000

    400000000000000

    8300000000000000

    Returns: 248

  173. 10

    1

    1000000000

    Returns: 268435454

  174. 10

    0

    10

    Returns: 1

  175. 0

    4

    4

    Returns: 1

  176. 0

    0

    4

    Returns: 5

  177. 3

    23

    23

    Returns: 0

  178. 20

    80

    85

    Returns: 6

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: