#! /usr/bin/python
# -*- coding: utf-8 -*-

'''
A positive integer N is given. The goal is to construct the shortest possible sequence of integers ending with N, using the following rules:
the first element of the sequence is 1; more specifically: A[0] = 1,
each of the following elements is generated by multiplying the previous element by 2 or increasing it by 1; more precisely: A = A[i−1] * 2 or A = A[i−1] + 1, for i ≥ 1.
For example, for N = 17, the shortest sequence is:
  A[0] = 1
  A[1] = 2
  A[2] = 4
  A[3] = 8
  A[4] = 16
  A[5] = 17
Write a function:
class Solution { public int solution(int N); }
that, given a positive integer N, returns the length of the shortest possible sequence of integers satisfying the above conditions and ending with N.
For example, given N = 17, the function should return 6, as explained above..
Assume that:
N is an integer within the range [1..2,147,483,647].
Complexity:
expected worst-case time complexity is O(log(N));
expected worst-case space complexity is O(1).
'''

def solution(N):
	steps = 1
	while N > 1:
		N = N/2
		steps += 1
	if N == 1:
		steps += 1
	return steps
		
print solution(17)

'''
2.A zero-indexed array A consisting of N integers is viven. We visit the indexs of the array in the following way. In the first step we visit the index 0; in every subsequent step we move from the visited index K to the index:
M = K + A[K];
provided M is within the array bounds. Otherwise, K is the last index visited. Write a funciton:. From 1point 3acres bbs
int solution(int A[], int N);
that, given an array A, returns the number of indexes that cannot be visited by the described procedure.
For example, for the array:
A[0] = 1
A[1] = 2
A[2] = 3
only index 2 cannot be visited, so the answer is 1.
For the array:. From 1point 3acres bbs
A[0] = 3
A[1] = -5
A[2] = 0.鏈枃鍘熷垱鑷�1point3acres璁哄潧
A[3] = -1.1point3acres缃�
A[4] = -3
indexes 1 and 4 cannot be visited, so the answer is 2.
Assume that:
N is an integer within the range [0...200,000];
each element of array A is an integer within the range [-1,000,000...1,000,000]
Complexity:
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N*log(N)), beyond input storage (not counting the storage required for input arguments).. 1point3acres.com/bbs
Elements of input arrays can be modified.
'''


