A machine has a screen initially displaying the number . The machine has two buttons: the left button adds to the number and the right button multiplies the number by .
Your task is to reach a given number by pushing the buttons. What is the smallest number of pushes needed?
For example, when , an optimal solution is the following:
- The initial number is .
- Push the left button to get the number .
- Push the left button to get the number .
- Push the right button to get the number .
- Push the left button to get the number .
In this case, the smallest number of pushes is .
In a file machine.py
, implement the function min_steps
that finds the smallest number of pushes to reach the number . If no sequence of pushes can achieve , the function should return .
The function should be efficient when is in the range .
def min_steps(x): # TODO if __name__ == "__main__": print(min_steps(1)) # 0 print(min_steps(2)) # 1 print(min_steps(3)) # -1 print(min_steps(4)) # 1 print(min_steps(5)) # 2 print(min_steps(17)) # 4 print(min_steps(42)) # -1 print(min_steps(100)) # 7 print(min_steps(1000)) # 13