Halve or Bump a Binary Number to One

Medium

You get a positive integer written in binary as a string bits with no leading zeros. Repeat one action until the number equals 1: - if the number is even, divide it by 2; - if it is odd, add 1 to it. Return how many actions this takes. Note that the string can be hundreds of characters long.

Example 1

bits="1011" → 6

This is 11: 11 → 12 → 6 → 3 → 4 → 2 → 1, which takes 6 steps.

Example 2

bits="100" → 2

This is 4: two halvings, 4 → 2 → 1.

Example 3

bits="1" → 0

Constraints

1 ≤ len(bits) ≤ 500
bits consists of the characters '0' and '1'
bits[0] = '1'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation String

Similar problems

Recurring Gene Windows Medium Words With No Shared Letters Medium Every Shorthand of a Word Medium Fewest Address Blocks Medium Every Case Spelling Medium

Input

bits="1011"

Expected

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.