Statistics

Problem Statement for "PrimeStrings"

Problem Statement

In this problem we deal with binary representations of integers. For clarity, decimal numbers will be given as numbers and their binary representations as strings. For example, the binary representation of 47 is "101111".

Additionally, in the entire problem statement, k is a positive integer constant. (The value of k will be given to you as one of the inputs.)

Let A be a positive integer. Consider the following process:

  1. Find the string S that is the binary representation of A.
  2. Let L = max( 1, length(S)-k ).
  3. Let T be any (not necessarily contiguous) subsequence of S such that the length of T is between 1 and L, inclusive.
  4. Convert T to decimal and output the result.

Each integer B that can be the result of the above process is called a binary substring of A. Note that S never starts with a leading zero, but T might. Some examples are shown below.

  • Let A = 10 and k = 1.
    1. We convert A to S = "1010".
    2. Then we compute that L = 3, which means that we are interested in subsequences of length at most 3.
    3. Hence, T is one of "0", "1", "00", "01", "10", "11", "010", "100", "101", or "110".
    4. This means that the binary substrings of A are 0, 1, 2, 3, 4, 5, and 6.
  • Let A = 10 and k = 2. Now we have L = 2, which means that the possible values of T are "0", "1", "00", "01", "10", and "11". Thus, the binary substrings of A are 0, 1, 2, and 3.
  • For A = 10 and k >= 3 the only binary substrings of A are the integers 0 and 1.
  • For A = 15 and k = 1 the binary substrings of A are the integers 1, 3, and 7.

You are given the int k. You are also given longs x and y. Consider the integers between 1 and x, inclusive, such that their largest binary substring is smaller than or equal to y.

Compute and return the number of such integers.

Definition

Class:
PrimeStrings
Method:
getCount
Parameters:
long, long, int
Returns:
long
Method signature:
long getCount(long x, long y, int k)
(be sure your method is public)

Constraints

  • x will be between 1 and 1012, both inclusive.
  • y will be between 1 and 1012, both inclusive.
  • k will be between 1 and 40, both inclusive.

Examples

  1. 2

    1

    1

    Returns: 2

    Given that k=1, the only binary substring of 1 is 1, and the binary substrings of 2 are 0 and 1. In both cases, the largest binary substring is less than or equal to y=1. Thus, the answer is 2.

  2. 6

    2

    1

    Returns: 4

    As x=6, we are interested in the numbers between 1 and 6, inclusive. For k=1, the largest binary substrings of 1, 2, 3, 4, 5, and 6 are 1, 1, 1, 2, 3, and 3, respectively. As we only count those for which the largest binary substring does not exceed 2, the answer is 4.

  3. 6

    1

    3

    Returns: 6

  4. 31

    6

    2

    Returns: 20

  5. 413

    34

    2

    Returns: 130

  6. 1000000000

    1000000000

    5

    Returns: 1000000000

  7. 549755813602

    8369864093

    5

    Returns: 178429547459

  8. 1

    1

    1

    Returns: 1

  9. 1

    1

    2

    Returns: 1

  10. 2

    1

    1

    Returns: 2

  11. 2

    1

    2

    Returns: 2

  12. 2

    2

    1

    Returns: 2

  13. 2

    2

    2

    Returns: 2

  14. 1000000000000

    8589934591

    5

    Returns: 274877906943

  15. 1000000000000

    8589934591

    6

    Returns: 549755813887

  16. 1000000000000

    8589934591

    7

    Returns: 1000000000000

  17. 1000000000000

    8589934591

    8

    Returns: 1000000000000

  18. 999999999999

    8589934591

    5

    Returns: 274877906943

  19. 999999999999

    8589934591

    6

    Returns: 549755813887

  20. 999999999999

    8589934591

    7

    Returns: 999999999999

  21. 999999999999

    8589934591

    8

    Returns: 999999999999

  22. 999999999998

    8589934591

    5

    Returns: 274877906943

  23. 999999999998

    8589934591

    6

    Returns: 549755813887

  24. 999999999998

    8589934591

    7

    Returns: 999999999998

  25. 999999999998

    8589934591

    8

    Returns: 999999999998

  26. 461676937380

    654316600

    8

    Returns: 137556399160

  27. 908109542027

    117401560

    10

    Returns: 68937152082

  28. 608255817586

    51239042

    9

    Returns: 17205720349

  29. 129585098534

    202002738

    2

    Returns: 606008216

  30. 98423914896

    1167807506

    2

    Returns: 4389032978

  31. 676759240994

    1997549437

    5

    Returns: 38995748181

  32. 159114673004

    1744932506

    2

    Returns: 5234797520

  33. 915664659517

    1873660725

    3

    Returns: 10178997463

  34. 125133074187

    443378842

    1

    Returns: 752539957

  35. 34359738199

    8149542948

    1

    Returns: 14881431699

  36. 34359738199

    4095361993

    2

    Returns: 13573203427

  37. 34359738199

    2127828527

    3

    Returns: 14837668479

  38. 34359738199

    509506477

    4

    Returns: 5484695753

  39. 34359738199

    225991385

    5

    Returns: 4510064923

  40. 34359738199

    8116

    20

    Returns: 4299738513

  41. 34359738199

    4039

    21

    Returns: 4296639263

  42. 34359738199

    2001

    22

    Returns: 4295425323

  43. 34359738199

    958

    23

    Returns: 4294989523

  44. 34359738199

    436

    24

    Returns: 4294968748

  45. 34359738199

    202

    25

    Returns: 4294967645

  46. 68719476128

    16247854512

    1

    Returns: 29557937859

  47. 68719476128

    7666944982

    2

    Returns: 23453091593

  48. 68719476128

    3605736099

    3

    Returns: 19791653519

  49. 68719476128

    1499836572

    4

    Returns: 17605963932

  50. 68719476128

    232745066

    5

    Returns: 4550587009

  51. 68719476128

    16376

    20

    Returns: 8803692302

  52. 68719476128

    8142

    21

    Returns: 8600876117

  53. 68719476128

    4023

    22

    Returns: 8591149647

  54. 68719476128

    2030

    23

    Returns: 8592181847

  55. 68719476128

    1015

    24

    Returns: 8591330087

  56. 68719476128

    431

    25

    Returns: 8589935967

  57. 137438953079

    33996879255

    1

    Returns: 66005451151

  58. 137438953079

    16905404183

    2

    Returns: 60844405351

  59. 137438953079

    7838853003

    3

    Returns: 44028791671

  60. 137438953079

    3809615883

    4

    Returns: 38890627251

  61. 137438953079

    1907209944

    5

    Returns: 37098618828

  62. 137438953079

    32704

    20

    Returns: 17290703240

  63. 137438953079

    16336

    21

    Returns: 17231945255

  64. 137438953079

    8191

    22

    Returns: 34359738367

  65. 137438953079

    4018

    23

    Returns: 17181187145

  66. 137438953079

    1951

    24

    Returns: 17180011295

  67. 137438953079

    949

    25

    Returns: 17179891721

  68. 274877905969

    68635488867

    1

    Returns: 136548844931

  69. 274877905969

    34083070889

    2

    Returns: 127333969137

  70. 274877905969

    17040301928

    3

    Returns: 119691075319

  71. 274877905969

    8375102454

    4

    Returns: 97436206473

  72. 274877905969

    3785967068

    5

    Returns: 73599728416

  73. 274877905969

    65469

    20

    Returns: 34767892781

  74. 274877905969

    32730

    21

    Returns: 34615299626

  75. 274877905969

    16298

    22

    Returns: 34391610251

  76. 274877905969

    8106

    23

    Returns: 34367056631

  77. 274877905969

    4023

    24

    Returns: 34361356391

  78. 274877905969

    1980

    25

    Returns: 34359990299

  79. 549755813602

    137102493885

    1

    Returns: 271649359343

  80. 549755813602

    68297629430

    2

    Returns: 258234344195

  81. 549755813602

    34281391361

    3

    Returns: 257960073455

  82. 549755813602

    16861002788

    4

    Returns: 202628264477

  83. 549755813602

    8369864093

    5

    Returns: 178429547459

  84. 549755813602

    131015

    20

    Returns: 70429538423

  85. 549755813602

    65477

    21

    Returns: 69359363603

  86. 549755813602

    32741

    22

    Returns: 69207187553

  87. 549755813602

    16309

    23

    Returns: 68763892103

  88. 549755813602

    8157

    24

    Returns: 68748453953

  89. 549755813602

    4045

    25

    Returns: 68723515403

  90. 4

    1

    1

    Returns: 3

  91. 8

    5

    1

    Returns: 8

  92. 641381782850

    2863311530

    5

    Returns: 69435304618

  93. 641381782850

    2863311530

    6

    Returns: 138154781354

  94. 641381782850

    2863311530

    7

    Returns: 275593734826

  95. 641381782850

    2863311530

    8

    Returns: 550471641770

  96. 641381782850

    2863311530

    9

    Returns: 641381782850

  97. 641381782850

    2863311530

    38

    Returns: 641381782850

  98. 641381782850

    2863311530

    39

    Returns: 641381782850

  99. 641381782850

    2863311530

    40

    Returns: 641381782850

  100. 999999999963

    9999999927

    4

    Returns: 138849018807

  101. 100000000000

    100000000000

    4

    Returns: 100000000000

  102. 981248851958

    809203166

    10

    Returns: 550067114132

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: