#!/usr/bin/python2

# Fuel Injection Perfection
# =========================

# Commander Lambda has asked for your help to refine the automatic quantum
# antimatter fuel injection system for her LAMBCHOP doomsday device. It's a
# great chance for you to get a closer look at the LAMBCHOP - and maybe sneak
# in a bit of sabotage while you're at it - so you took the job gladly.

# Quantum antimatter fuel comes in small pellets, which is convenient since the
# many moving parts of the LAMBCHOP each need to be fed fuel one pellet at a
# time. However, minions dump pellets in bulk into the fuel intake. You need to
# figure out the most efficient way to sort and shift the pellets down to a
# single pellet at a time.

# The fuel control mechanisms have three operations: 

# 1) Add one fuel pellet

# 2) Remove one fuel pellet

# 3) Divide the entire group of fuel pellets by 2 (due to the destructive
# energy released when a quantum antimatter pellet is cut in half, the safety
# controls will only allow this to happen if there is an even number of
# pellets)

# Write a function called solution(n) which takes a positive integer as a
# string and returns the minimum number of operations needed to transform the
# number of pellets to 1. The fuel intake control panel can only display a
# number up to 309 digits long, so there won't ever be more pellets than you
# can express in that many digits.

# For example:
# solution(4) returns 2: 4 -> 2 -> 1
# solution(15) returns 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1

def change(b, n):
  a = int("".join([str(x) for x in b]), 2) + n
  return [int(i) for i in list("{0:b}".format(a))]

def solution(n):
  if n == "1": return 0
  if n == "2": return 1
  
  b = [int(i) for i in list("{0:b}".format(int(n, 10)))]

  c = 0
  
  flag = True
  while flag == True:
    if (len(b) <= 2):
      flag = False
      continue
    if b[-1] == 0:
      c += 1
      b.pop()
    else:
      if b[-2] == 1:
        c += 1
        b = change(b, 1)
      else:
        c += 1
        b = change(b, -1)

  if b[1] == 1:
    c += 2
  else:
    c += 1

  return c

def funny_add1(b):
  b.reverse()

  carry = 0
  for i in range(0, len(b)):
    if b[i] == 0:
      b[i] = 1
      break
    else: #if b[i] == 1:
      b[i] = 0
      carry = 1
    if i == len(b) - 1 and carry == 1:
      b.append(1)

  b.reverse()
  return b

print(solution("19"))
print(solution("4")) # => 2
print(solution("15")) # => 5