Last Updated: 1 Dec, 2020
Minimum Number Of Stabs To Kill King
Moderate
Asked in companies
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
Approaches
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.
- 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.
- 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’.
- 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.
- We can get from ‘X’ + 1 to ‘X’ using the first type of stab.
- We can get from 2*X, 3*X, ….(X)*X to X, as max('H1', ‘H2’) will be value X.
- Recursion idea is similar except, one more constraint is added that ‘i’*'X' <= ‘N’, which is obvious.
- We also want to minimise the number of stabs, so at every point of transitions, try to minimise the number of transitions.
- You can apply recursion from left to right or from right to left i.e from 1 to ‘N’ or from ‘N’ to 1
- Here we have applied recursion from left to right(1 to 'N').
In the recursion, we were calculating the same subproblem multiple times. We can optimise this algorithm by avoiding repeatedly solving the same subproblem and storing the answer for a subproblem once calculated.
Here is the algorithm :
- Create an array (say, ‘DP’) of size ‘N’ + 1, where ‘DP’[i] will store the minimum number of stabs to reduce health from i to 0.
- In reverse, you can think of this problem as increasing health from 0 to i in the minimum number of steps.
- Initially, populate the ‘DP’ array with INT_MAX large value.
- Do transitions similar to recursion approach and memoizing the solution for each value of heath i in ‘DP’[i].
- The transitions in recursion after applying memoisation (if the current health of the king is ‘i’) will be:
- ‘DP’[i + 1] is equal to min('DP'[i + 1], ‘DP’[i] + 1), that is, if first kind of stab was used so that kings final health was ‘i’, then minimise the no of stabs required at health ‘i’ + 1 to ‘DP’[i]+1.
- Else, we can apply second stab : where ‘next_i’ = ‘i1’*'i2', and if ‘i1’ >= ‘i2’, then 'i' = ‘i1’. That means, that ‘next_i’ can range from 2*'i1' to min('N', ‘i1'*'i1'), with increments of ‘i’ in ‘i2’, to satisfy property of ‘next_i’ = ‘i1’*'i2'. Minimise all the values that are reachable from ‘i’ using this transition. In other words, we know the minimum number of stabs to kill the king if his health was i, then in the current step minimise, the number of steps to kill the king if its multiple of ‘i’.
- ‘DP’[next_i] = min('DP'[next_i], ‘DP’[i] + 1);
- Finally, return ‘DP’[N].
Similar problems