Basically we have some binary number. Its number of bits may be up to 2 * 10^5. There can be trailing and leading 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.
Upd: 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