You are viewing a single comment's thread. Return to all comments →
The problem can be solved most efficiently using bit-manipulation. Once again the editorial disappointed me. "Discussions" has better solutions than the editorial. Anyways, the problem can be solved in O(b) complexity, where b=consecutive 1's :
n = int(input())
ans = 0
while n>0 :
n &= (n<<1)
ans += 1
"Logical-and" accompanied with "left-shift" reduces consecutive set-bits(1's) by 1. Thus, counting these operations gives the required answer.