# 谷歌店面挂经

You are allowed three operations (each ofthese is considered a ‘hop’), these are:

• Divide by 3

• Divide by 2

• Subtract 1

Given a positive integer as input, computethe minimum number of hops to reduce the number down to 1.

7:

subtract 1 -> 6

divide by 3 -> 2

subtract 1 -> 1

10:

subtract 1 -> 9

divide 3 -> 3

divide 3 -> 1

``````fn = min(fn -1, fn/2, fn/3)+1

def num_hops(n):

f= [n]*(n+1)

f[1] = 0

for i in range(1,n):

if i*3 <= n:

f[i*3] = min(f[i*3],f+1)

if i*2 <= n:

f[i*2] = min(f[i*2],f+1)

if i+1 <= n:

f[i+1] = min(f[i+1],f+1)

return f[n]

i 1  2   3   4  5   6   7  8   9   10

f 0  1   1   2  3   2   3  3   2   3

``````

Ram was driving past a street with a lot ofhigh rise buildings. Ram wondered, were there any three buildings such thateach is double the height of the previous one. Could you help him figure outthat?

Assume that heights are whole numbers.

Main question: Can you find out how manysuch occurrences are there?

3, 1, 2, 7, 4

return 1

3 1 2 7 4 4 1

return 2