KleofasTail | Topcoder Archive

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

```
3
```
```
4
```
```
8
```
```
Returns: 2
```
The value 3 occurs in the Kleofas tail of 6 and also in the Kleofas tail of 7.
```
1
```
```
23457
```
```
123456
```
```
Returns: 100000
```
For each X between 23457 and 123456, inclusive, the Kleofas tail of X contains the value 1.
```
1234567890123456
```
```
10
```
```
1000000
```
```
Returns: 0
```
Each Kleofas tail is a nonincreasing sequence.
```
0
```
```
0
```
```
2
```
```
Returns: 3
```
```
2
```
```
3
```
```
3
```
```
Returns: 1
```
The Kleofas tail of 3 is 3, 2, 1, 0, 0, 0, ...
```
13
```
```
12345
```
```
67890123
```
```
Returns: 8387584
```

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.