PROBLEM LINK:
Author: Himanshu
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
EXPLANATION:
Consider the interval (2k, x], where k = floor(log2). 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 = 100101012 and i = 4, t = 10012. 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 2i-1(100002… (i – 1 zeroes)) to t – 1 is also a repeating block. For example, for i = 4, t = 10012 and x = 100111012, p = 100110012. Clearly 10002 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 101010102. For i=4, g[i] = 1 + (10102 – 10002) = 3. The blocks are 10102, 10012 and 10002. For i = 2 (another divisor), g[i] = 1 + (102 – 102) = 1. The block is 102. Given the above blocks, clearly the number 101010102 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 (2k, x] (k = floor(log2)).
Clearly, the binary representation of 2k does not have a repeating block of any size…
We can now set x = 2k – 1 to get the result of the interval (2k-1, 2k – 1]. Similarly, next time we set x = 2k-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(log2(y) * log2(y))