Author: Adlet Zeineken
Tester: Misha Chorniy
Editorialist: Bhuvnesh Jain
You 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.
The 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:
Thus, the overall probability of obtaining A on the first throw and B on the second throws is given by:
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
def count_frequency(array a, integer x): count = 0 for number in a: if number == x: count += 1 return count
The constraints of the problem were such that all the operations can be done in integers only without any overflow issues.
O(n) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution can be found here.
Editorialist’s solution can be found here.