EllysCode01 | Topcoder Archive

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:

Copy the entire sequence, but change each zero into a one and vice versa.
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

```
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.
```
101
```
```
185
```
```
Returns: 42
```
The answer is 42.
```
0
```
```
0
```
```
Returns: 0
```
The digit at index zero is 0.
```
1
```
```
1
```
```
Returns: 1
```
The digit at index one is 1.
```
1337
```
```
1337
```
```
Returns: 0
```
The digit at 1337-th position is 0.
```
12345
```
```
67890
```
```
Returns: 27772
```

5192834871235435

954971273487212547

Returns: 474889219307988557

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.