Problem LinkAuthor: Adlet Zeineken Tester: Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyCAKEWALK PrerequisitesProbability, Looping ProblemYou are given an N sided dice. You roll it twice and need to find the probability of getting A on the first throw and B on the second throw. ExplanationThe probability of obtaining a number on the consecutive throw of a dice is independent of each other. For more details, you may refer here. The probability of getting a number $X$ on throwing a $N$ sided dice is given by: $$\text{Probability} = \frac{\text{Number of times X appears on the dice}}{N}$$ Thus, the overall probability of obtaining A on the first throw and B on the second throws is given by: $$\text{Required Probability} = \frac{\text{Number of times A appears on the dice}}{N} * \frac{\text{Number of times B appears on the dice}}{N}$$ Thus, the problem reduces to finding the frequency of a number in an array. This can be easily done in $O(1)$ space complexity and $O(n)$ time complexity using a simple for loop as below
The constraints of the problem were such that all the operations can be done in integers only without any overflow issues. Time Complexity$O(n)$ per test case. Space Complexity$O(1)$ AUTHOR'S AND TESTER'S SOLUTIONS:Tester's solution can be found here. Editorialist's solution can be found here.
This question is marked "community wiki".
asked 06 Jun '18, 01:25

Video solution (with a comparison of 3 different solutions): https://youtu.be/r9yvzd0tTJQ answered 13 Jun '18, 18:42
