# PROBLEM LINK:

* Author:* Himanshu

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

# EXPLANATION:

Consider the interval (2^{k}, x], where k = floor(log_{2}). Clearly binary representation of every number in the interval has length len = k + 1 (without leading zeros).

Let’s assume a repeating block in a binary representation of length len, has length i where i is a divisor of len (i \ne len) and there are g[i] such blocks.

To calculate g[i], we first get first i bits of the binary representation as t = x >> (len – i). For example for x = 10010101_{2} and i = 4, t = 1001_{2}. For p = tttt… ((len / i) times) if p <= x, then set g[i] = 1 otherwise 0. p can be calculated by looping over p = (p << i) + t. Clearly, every correct block should begin with 1 and should be less than or equal to t.

Next, we can see that every block from 2^{i-1}(10000_{2}… (i – 1 zeroes)) to t – 1 is also a repeating block. For example, for i = 4, t = 1001_{2} and x = 10011101_{2}, p = 10011001_{2}. Clearly 1000_{2} is also a repeating block. So, g[i] = g[i] + t – (1 << (i – 1)).

We can sum g[i]’s for all i’s such that i is a divisor of len(i != len) to get the result for the interval. However, there is a catch.

Consider the case of 10101010_{2}. For i=4, g[i] = 1 + (1010_{2} – 1000_{2}) = 3. The blocks are 1010_{2}, 1001_{2} and 1000_{2}. For i = 2 (another divisor), g[i] = 1 + (10_{2} – 10_{2}) = 1. The block is 10_{2}. Given the above blocks, clearly the number 10101010_{2} has been counted twice. This can be resolved by subtracting g[j] from g[i] for all j such that j divides i and j < i.

Now we can sum all g[i]’s to get the correct result for the interval (2^{k}, x] (k = floor(log_{2})).

Clearly, the binary representation of 2^{k} does not have a repeating block of any size…

We can now set x = 2^{k – 1} to get the result of the interval (2^{k-1}, 2^{k} – 1]. Similarly, next time we set x = 2^{k-1}, and continue so on until x = 1. Clearly, the intervals are non-intersecting and we can sum the result we get from every interval to get the answer for the interval [1, x]. If f(x) denotes this answer, the answer to the problem is f(y) – f(x – 1), for the interval [x, y].

### COMPLEXITY:

O(log_{2}(y) * log_{2}(y))