INF = 10000000000 def sum_of_1 n sum = 0 while n > 0 do sum += n % 2 n /= 2 end return sum end n = gets.to_i dist = {} (n+1).times {|i| dist[i] = INF } queue = Queue.new queue.push(1) dist[1] = 1 while true do if queue.size == 0 break end val = queue.pop() diff = sum_of_1 val right = val + diff left = val - diff if right === n || left === n puts (dist[val] + 1) exit end if right < n && dist[right] == INF dist[right] = dist[val] + 1 queue.push(right) end if left > 0 && dist[left] == INF dist[left] = dist[val] + 1 queue.push(left) end end puts(-1)