func integerReplacement(n int) (cnt int) {
	for n&1 == 0 {
		cnt++
		n >>= 1
	}
	if n == 1 {
		return
	}
	return cnt + 1 + minInt(integerReplacement(n-1), integerReplacement(n+1))
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}