CSES - Machine

A machine has a screen initially displaying the number 11. The machine has two buttons: the left button adds 33 to the number and the right button multiplies the number by 22.

Your task is to reach a given number xx by pushing the buttons. What is the smallest number of pushes needed?

For example, when x=17x=17, an optimal solution is the following:

  • The initial number is 11.
  • Push the left button to get the number 44.
  • Push the left button to get the number 77.
  • Push the right button to get the number 1414.
  • Push the left button to get the number 1717.

In this case, the smallest number of pushes is 44.

In a file machine.py, implement the function min_steps that finds the smallest number of pushes to reach the number xx. If no sequence of pushes can achieve xx, the function should return 1-1.

The function should be efficient when xx is in the range 110001 \dots 1000.

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