How to solve codeforces Bits problem?

general
1

Please tell me - How to solve codeforces Bits problem?

2

There is already a tutorial available on their site. Did you find any difficulty in understanding that?

[Edit] The brute force approach is that iterate from l to r and finding the count of set bits, also keeping track of the maximum set bits. This will time out even if you use the best algo to count the set bits.

Better approach is increment by exponents of 2, 2^i, 0 <= i <= b, you need to keep increment i such that l <= 2^i -1 <= r, if you reach this case, then 2^i-1 is the required result. This is because 2^i contains just one set bit, and 2^i-1 contains i set bits. There is another case in which 2^i-1 lies out side the range of [l,r], I will update that case later.

1 Like
3

It could not understand.

4

Let me explain a little more in my answer.

5

Actually , i can not understand the problem?

6

In simple words, you have to find the non-negative integer X such that L <= X <= R and X has the maximum number of its bits set to 1 in its binary representation.

For example :-

If L = 0 , R = 15

0 = 0000     8 = 1000
1 = 0001     9 = 1001
2 = 0010    10 = 1010
3 = 0011    11 = 1011
4 = 0100    12 = 1100
5 = 0101    13 = 1101
6 = 0110    14 = 1110
7 = 0111    15 = 1111

As you can see, in the given case X = 15 has the most number of its bits set to 1. Thus X = 15 is the answer.

You can refer to the editorial for the solution.

1 Like