Minimum Number Of Stabs To Kill King

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
6 upvotes
Asked in companies
Rubrik, Inc.Amdocs

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
8
Sample Output 1 :
4
Explanation For Sample Input 1 :
We know that, 8 = 4*2. So, we can reduce kings health from 8 to 4 after one stab of type 2. 
Now since, 4 = 2*2, so after the second stab of type 2, king’s health reduces from 4 to 2. 
The current health of king = 2. After the third stab of type 1, the king’s health reduces from 2 to 1.
Finally, after the fourth stab of type 1, the king’s health reduces from 1 to 0.
So, in total it takes 4 steps at minimum to kill the king.
Sample Input 2 :
1
3
Sample Output 2 :
3
Hint

Try to generate all possible ways.

Approaches (2)
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.

 

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

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

Space Complexity

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

Code Solution
(100% EXP penalty)
Minimum Number Of Stabs To Kill King
Full screen
Console