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
0
22
Returns: 10
S[0:22] is the prefix shown in the problem statement: "0110100101100010011010". It contains 10 ones (and 12 zeros).1
22
Returns: 10
S[1:22] is "110100101100010011010" (the same as previous example, except for the initial zero). It still contains 10 ones.5
21
Returns: 7
S[5:21] is "0010110001001101".