Minimum Number Of Stabs To Kill King
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

Question

Minimum Number Of Stabs To Kill King

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

Accepted Answer

Recursion

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').

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the initial health of the king.

Recursive stack is called ‘N’ for calculating stab for health 1 to ‘N’. Hence, the overall space complexity will be O(N).

Time Complexity: OtherExplanation:

O(2 ^ sqrt(N)), where ‘N’ is the initial health of the king.

We call recursive function ‘N’ times for calculating the stabs for each subproblems generating all possible ways which can be up to 2 ^ 'N' and in which we run a loop over multiples of health in each call which can be maximum up to O(sqrt(N)). Hence, the overall time complexity will be O(2 ^ sqrt(N)).

Accepted Answer

Dynamic Programming.

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].

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the initial health of the king.

We use an extra array of size ‘N’ for storing answers. Hence, the overall time complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * sqrt(N)), where ‘N’ is the initial health of the king.

We run a loop over ‘N’ and a nested loop which can run up to multiples of ‘i' which is the maximum of O(sqrt(i)) for the ‘i’th iteration. Hence, the overall time complexity will be O(N * sqrt(N)).

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):

Note :

Input Format :

Output Format :

Note :

Constraints :

Top RUBRIK INDIA Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern