how to derive this formula for save the king

general
1

how the answer is

2*(n-pow(2,log2(n))+1

Can anbody explain?

2

Though i can explain it, i would recommend u to give it a try after considering the following hint.

Try simulating the whole process, just write all numbers in binary representation, try finding out pattern… It will help u.

If u still feel problem, just put a comment here. :slight_smile:

3

This Problem Can Be Solved With Simple Observation

For Input : 9 (1001)

Output : 3 (0011)

Similarly For Input: 12 (1100)

Output: 9 (1001)

Observation:

Most Significant Bit (M.S.B) In Binary Representation Of Input is moved To Least Significant Bit (L.S.B) In Binary Representation to get Output

4

can you give 1 example ?

5

I think you have asked a question similar to this kind of question

https://discuss.codechef.com/questions/118955/how-to-solve-this

I Guess You Can refer to @pk301 explanation for derivation of formula