Can the set bit be counted at each position throughout the range [L, R]? 1 <= L, R <= 10^12
Example : [5, 13]
5: 101
6: 110
7: 111
8: 1000
9: 1001
10: 1010
11: 1011
12: 1100
13: 1101
0th position : 5
1st position : 4
2nd position : 5
3rd position : 6
I think we can using digit dp on binary representation of number
Can you Implement it !!.
You Can Take Help From this
They Explain all way to explain this problem.
Bro Look at Constraint
You can see the O(LogN) 273619610 solution which describes in below of this page
It's not what it's
Digit Dp and maybe Gray code can be used. https://www.geeksforgeeks.org/what-is-gray-code/
Use the fact that the bits at ith position alternate after every 2^i numbers. So for a bit i, find the first number after L which has it set call it L_set, and first number below L which has it un-set called it L_unset this can be done in constant time. Similarly do it for R also, now that you know the range — [L_unset+1, R_unset-1] has a multiple of 2^i numbers and you know L_unset, L_set, R_unset and R_set you can subtract the out of range elements from this count.
So I've to find every first number that is set at ith index and then count the 2^i time.
no pre-computing is required we can do that at every query for L and R as it takes constant time, that's better imo
For i. bit,
$$$f(X)$$$ will give count of numbers in $$$1 \leq y \leq X$$$
You can see the contrubition pattern is $$$i$$$ number of 0s, $$$i$$$ number of 1s, $$$i$$$ number of 0s, etc.
So if $$$X$$$ equals $$$2^{(i + 1)} \times y$$$, count is $$$2^i \times y$$$
Else, divide it into 2 parts: $$$2^{(i + 1)} \times y$$$, and another part, $$$Z$$$, which is in $$$0 \leq Z \le 2^{(i + 1)}$$$, and the first part calculation is the same.
We can say for another part their contrubition pattern is $$$i$$$ numbers of 0 and $$$i$$$ number of 1. (Not any more)
If it is smaller than $$$2^i$$$, its contribution is 0
Else its contrubition is $$$Z - 2^i$$$
And answer for i. bit is $$$f(R) - f(L - 1)$$$
Bro it's hard to be understand can you simplify it.