Statistics

Problem Statement for "SparseOnes"

Problem Statement

Consider all non-negative integers written in binary.

In this problem we'll call a non-negative integer good if its binary representation doesn't contain two consecutive ones. For example, 0, 2, 5, 10, 16 and 41 are good (in binary they are 0, 10, 101, 10000, 101001) while 3, 6, 11 are bad (in binary: 11, 110, 1011).

Let's take all good non-negative integers in order and let's concatenate their binary representations to get an infinite binary string S. The first few of these representations are 0, 1, 10, 100, 101, 1000, 1001, 1010 and thus the string begins S = 0110100101100010011010...

You are given the longs A and B. Calculate and return the sum of digits of (i.e., the number of ones in) the substring S[A:B].

Definition

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

Notes

  • The substring S[x:y] contains of characters whose 0-based indices lie in the half-open interval [x,y).

Constraints

  • 0 <= A < B <= 10^14.

Examples

  1. 0

    22

    Returns: 10

    S[0:22] is the prefix shown in the problem statement: "0110100101100010011010". It contains 10 ones (and 12 zeros).

  2. 1

    22

    Returns: 10

    S[1:22] is "110100101100010011010" (the same as previous example, except for the initial zero). It still contains 10 ones.

  3. 5

    21

    Returns: 7

    S[5:21] is "0010110001001101".

  4. 0

    100000000000000

    Returns: 28502454998808

  5. 0

    1

    Returns: 0

  6. 0

    36

    Returns: 15

  7. 0

    122

    Returns: 45

  8. 0

    863

    Returns: 291

  9. 1

    29

    Returns: 12

  10. 1

    70

    Returns: 27

  11. 1

    68

    Returns: 26

  12. 2

    4

    Returns: 1

  13. 2

    33

    Returns: 13

  14. 2

    262

    Returns: 92

  15. 3

    62

    Returns: 22

  16. 3

    14

    Returns: 4

  17. 3

    442

    Returns: 150

  18. 4

    193

    Returns: 70

  19. 4

    5

    Returns: 1

  20. 4

    57

    Returns: 20

  21. 5

    361

    Returns: 128

  22. 5

    13

    Returns: 3

  23. 5

    11

    Returns: 3

  24. 6

    9

    Returns: 1

  25. 6

    910

    Returns: 302

  26. 6

    391

    Returns: 135

  27. 7

    9

    Returns: 1

  28. 7

    52

    Returns: 18

  29. 7

    163

    Returns: 57

  30. 8

    117

    Returns: 40

  31. 8

    31

    Returns: 8

  32. 8

    397

    Returns: 135

  33. 9

    43

    Returns: 14

  34. 9

    216

    Returns: 74

  35. 9

    925

    Returns: 307

  36. 31094702574474

    73099184643215

    Returns: 11950244039897

  37. 16035717147238

    53460347362137

    Returns: 10753276555698

  38. 35624543524973

    84941406479794

    Returns: 14156610984522

  39. 2136505223538

    21000491886805

    Returns: 5392347278430

  40. 23970131422335

    88263927248246

    Returns: 18454882223604

  41. 10497255591190

    71950433529840

    Returns: 17515722768443

  42. 67063968125074

    87612233235939

    Returns: 6018675913407

  43. 51451284182047

    85538711181209

    Returns: 9767496823322

  44. 85657299996167

    89836577598124

    Returns: 1159798022297

  45. 29743692285830

    81192157255244

    Returns: 14698076812085

  46. 25897329037639

    60745208372917

    Returns: 9933369397728

  47. 27964192610880

    66117485378403

    Returns: 10866282220008

  48. 13847523786770

    80168936573125

    Returns: 18947980492520

  49. 15210164371266

    74222807547265

    Returns: 16864052523328

  50. 62475740464810

    91847877565853

    Returns: 8441897631968

  51. 51965097783734

    58274641872217

    Returns: 1732374458903

  52. 19761323651422

    37185915847401

    Returns: 4936520718678

  53. 28310238204991

    69624906047908

    Returns: 11750694154322

  54. 63838367843802

    79845862700013

    Returns: 4616759104320

  55. 24644839508091

    97813628094416

    Returns: 20848212535329

  56. 21190663288555

    76484441985389

    Returns: 15772530467783

  57. 6570729117460

    89439852142361

    Returns: 23716386128971

  58. 53300807146298

    87548087400379

    Returns: 9820952021171

  59. 3122970140800

    42602161094738

    Returns: 11255929149821

  60. 43299918333263

    86222495471036

    Returns: 12361621792198

  61. 21279565307967

    81593855645996

    Returns: 17244595830824

  62. 38443231901147

    80341613757979

    Returns: 11994561391747

  63. 48234592653856

    79229608326753

    Returns: 8847087969259

  64. 7342489351551

    16131696316105

    Returns: 2500571352317

  65. 58778403319624

    79419540839231

    Returns: 5917067224202

  66. 50000000000000

    100000000000000

    Returns: 14189298752323

  67. 5

    100000000000000

    Returns: 28502454998805

  68. 1000000000000

    100000000000000

    Returns: 28214585435847

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: