We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Tutorials
  3. LinkedIn Placements
  4. Consecutive 1's in Binary Numbers
  5. Discussions

Consecutive 1's in Binary Numbers

  • AbhishekVermaIIT
     + 11 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
print(ans)

    Logic :

    "Bitwise-and" accompanied with "left-shift" reduces consecutive set-bits(1's) by 1. Thus, counting these operations gives the required answer.