Practice Link

Author: Himanshu




Bitwise Operation


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].


O(log2(y) * log2(y))


Setter’s Solution