Hi all,
Sorry for the late reply. Anyway here is the solution...
I want to note down 2 facts...
1. With 1 one the maximum reachable is 1
2. Any sequence of move is exactly reversible. You just have to toggle the bits in reverse order.
Now the solution.
With n ones..
1. Use first n-1 ones to reach 2^(n-1) - 1
2. Set 2^(n-1) th one.
3. Reverse the first step.
4. Now use the n-1 ones to set the next 2^(n-1) - 1 ones!
So for n, we do three times n-1 and 1 more step to set the 2^(n-1)th element.
So the dp solution is,
dp[1] = 1
dp[n] = 3 * dp[n-1] + 1
Regards,
Prunthaban
