Actually this problem isn’t on this website but I have no idea where else to ask so.
Basically we have some binary number. Its number of bits may be up to 2 * 10^5. There can be leading and trailing zeros of course
Time limit = 1 sec
Memory limit = 256 Megabytes
For example
101. Let’s say that n is number of bits in this binary number. Here n = 3
For every i from 0 to n - 1 we want to do next thing:
invert i-th bit from left. So for example here if i = 0 we get 001, if i = 1 we get 111 etc
Then we do next thing. We do 001 mod (number of set bits in this binary number)
so we get 001 mod 1 = 0. if we get 0 we stop. If no then we again do (binary_number) mod (number of set bits in this binary number) etc.
We want to count how many this mod operation we must do to make a number equal to zero.
And we do this for every i from 0 to n - 1 again.
So for example
for i = 0 here we get 001 mod 1 = 0 we stop. 1 operation we print(1)
for i = 1 here we get 111 mod 3 = 1 => 001 mod 1 => 0 we stop. 2 operations we print(2)
for i = 2 here we get 100 mod 1 = 0 we stop. 1 operation we print(1)
I came up with the O(n^2) solution but it is TLE as we see 'cause of n restrictions. (n <= 2 * 10^5)
We need here time complexity O(n log n) i guess or something like that but i just can’t come up with a solution that has this time complexity.
I need help. if you have any ideas or questions about this problem please write them.
And also my guess is that the answer for every possible number in this problem is in interval [1;4]. But it’s just a guess based on tests that I generated and checked them with dummy n^2 solution