Mohan and Magic Boots

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
0 upvote
Asked in company
Walmart

Problem statement

Mohan is walking on a street, Assume he is walking on the X-Axis. He is currently at point ‘0’ and needed to reach a point ‘N’.

On the way, he found magic boots which have a special property, it makes him teleport either to point ‘X+2’ by a probability of ‘P/100’ or otherwise to point ‘X+3’ if he is currently on point ‘X’.

Now as he has some urgent work to do after reaching point ‘N’, he wants to calculate the probability of reaching point ‘N’, and if that probability is strictly greater than ‘X/100’ then it means he will reach the point ‘N’ earlier, otherwise walking without magic boots he will reach earlier.

Being his friend he asked you to help him to calculate the probability to reach point ‘N’ and help him decide if it's helpful to pick up the boots or not. If the probability is strictly greater than ‘X/100’ you say ‘1’ or else you say ‘0’. Can you help him?.

EXAMPLE : 
Input: ‘N’ = 2, ‘P' = 30, ‘X’ = 29

Output: 1
In this case, 
The probability to reach point ‘2(=N)’ while wearing the magic boots is 
‘P/100’ = 30/100 = 0.30 i.e. 0.30 > (‘X/100’ = 29/100 = 0.29). Hence the output will be ‘1’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer ‘T’, the number of test cases.

Each test case consists of one line.

The first line of input contains three integers, ‘N’, ‘P’, and ‘X’ separated by spaces.
Output format : 
For each test case, print ‘1’ or ‘0’ depending on the above-mentioned conditions.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
1 <= ‘P’ <= 100
1 <= ‘X’ <= 100
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
Time Limit: 1 sec
Sample Input 1 :
2
3 17 12
4 16 10
Sample Output 1 :
1
0
Explanation Of Sample Input 1 :
For the first test case, the probability of reaching point ‘3(=N)’ by wearing magic boots is ‘(100-P)/100’ = 83/100 = 0.83, which is greater than ‘X/100’ = 12/100 = 0.12.

Hence, the output will be: 1

For the second test case, the probability of reaching point ‘4(=N)’ by wearing magic boots and first getting teleported to point ‘2’ with a probability ‘P/100’ and then again getting teleported to point ‘4’ with a probability ‘P/100’ i.e. overall probability is ‘(P/100)*(P/100)’ = (16/100)*(16/100) = 256/10000 = 0.0256, which is less than ‘X/100’ = 10/100 = 0.10.

Hence, the output will be: 0
Sample Input 2 :
2
5 20 31
10 40 36
Sample Output 2 :
1
0
Hint

Are there any sub-problems involved in the main problem?.

Approaches (3)
Recursion

The idea for this approach is to divide the problem into subproblems, calculate their answers individually and then merge them for the main problem.
 

Here in this problem, when we are at some point ‘X’ then we calculate the probability to reach point ‘N’ from point ‘X+2’, and then multiply the probability to reach ‘X+2’ (i.e. ‘P/100’) by it. Similarly, we calculate the probability to reach point ‘N’ from point ‘X+3’, and then multiply the probability to reach ‘X+3’ (i.e. ‘(100-P)/100’) by it, Then we add both these probabilities to find the probability to reach point ‘N’ from point ‘X’.
 

Thus the above idea, shows there are two sub-problems involved with every main problem. Thus it can be solved using a recursive algorithm that will return the probability to reach point ‘N’ from that point.

 

Algorithm:
 

// This function will return the probability to reach point ‘N’ from the index ‘i’.

Double getProbability(I, N, P)

  • If ‘I>=N’
    • Return ‘(Double)(I==N)’.
  • Initialize the variable ‘ANS’ with the value of ‘(P/100)*getProbability(I+2, N, P)’.
  • Add ‘((100-P)/100)*getProbability(I+3, N, P)’ to ‘ANS’.
  • Return ‘ANS’.

 

// The function will return if the magic boots should be worn by Mohan or not.

Int canWear(N, P, X)

  • Initialize the variable ‘ANS’ with the value of ‘getProbability(0, N, P)’.
  • Initialize the variable ‘minProbability’ with the value of ‘X/100’.
  • If ‘ANS > minProbability’
    • Return ‘1’
  • Return ‘0’.
Time Complexity

O(2^N), Where ‘N’ is the input integer.

In our above-explained algorithm, for every index from ‘0’ to ‘N’, we will calculate the answer for two subproblems which will lead to the calculation of four subproblems and so on, thus there are (2^N) possibilities explored overall.

Hence the time complexity will be O(2^N)

Space Complexity

O(N), Where ‘N’ is the input integer.

 

In our above-explained algorithm, there will be the use of recursion stack space of ‘N+1’ as we will visit ‘N+1’ points at max.

Hence the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Mohan and Magic Boots
Full screen
Console