Minimum Number Of Stabs To Kill King

Posted: 1 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given the health of the king as an integer 'N'. You need to find the minimum number of stabs to kill the king. The king dies if the health becomes 0.

At any point, to decrease the health of the king you can apply either of two operations (types of stab):

1. The first kind of stab decreases the king’s health 'H' by 1 i.e 'H' = 'H'-1.
2. The second kind of stab decreases the king’s health to 'H1', where 'H'= 'H1'*'H2' and 'H1' >= 'H2' > 1 i.e if 'H' = 'H1'*'H2', then 'H' can decrease to 'H1' where 'H1' is the larger factor.

Note :

1. The king’s initial health is an integer and always positive.
2. After each step, the king’s health is decreased. It can not remain the same after a stab of either type.
Input Format :
The first line of the input contains an integer 'T', denoting the number of test cases.

The first line and the only line of each test case contains an integer 'N', denoting the initial health of the king.
Output Format :
The only line of output of each test case should contain a value denoting the minimum number of stabs required to kill the king.
Note :
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10^2
1 <= N <= 10^3

Time Limit : 1sec
Approach 1

Let’s try to do this problem using recursion, as the problem follows optimal substructure property. That is from any particular value say ‘X’, there are limited possible transitions that you could make.

 

  1. If the value of ‘N’ is equal to 1, then we can use only the first kind of stab to kill the king, i.e. do -1 to reduce the health to 0, and the king shall die.
  2. Base Case for recursion is when current health ‘X’ becomes equal to ‘N’, then return 0, as we want to kill the king with initial health ‘N’.
  3. In other cases, let’s think if we are at some health ‘X’, then what all values of health can be reduced to ‘X’ using two types of stab.
  4. We can get from ‘X’ + 1 to ‘X’ using the first type of stab.
  5. We can get from 2*X, 3*X, ….(X)*X  to X, as max('H1', ‘H2’) will be value X.
  6. Recursion idea is similar except, one more constraint is added that ‘i’*'X' <= ‘N’, which is obvious.
  7. We also want to minimise the number of stabs, so at every point of transitions, try to minimise the number of transitions.
  8. You can apply recursion from left to right or from right to left i.e from 1 to ‘N’ or from ‘N’ to 1
  9. Here we have applied recursion from left to right(1 to 'N').
Try Problem