Tried my best to think through during the interview but I failed to arrive at a valid answer. Will appreciate if anyone can propose candidate solutions

• Given that microwave takes key stroke inputs, a target cooking time and the following costs for input, find optimal input
  • Input 999 will be interpreted as 9 minutes 99 seconds, 81 as 81 seconds, 1221 as 12 minutes 21 seconds
  • Cost of each key stroke is 1, cost of moving the finger to a different key is 2 || 999 cost is 3, 1122 cost is 6, 1234 cost is 10
  • Input has to be within 10% of target time. If the cost is same, select the input that's closest to the target
  • Ex: for target time of 10 minutes, 888 is optimal(not 999)