NAICHEF - Editorial

editorial
, , , , ,
1

Problem Link

Practice

Contest

Author: Adlet Zeineken

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

Probability, Looping

Problem

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.

Explanation

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:

\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


	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.

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.

2

Video solution (with a comparison of 3 different solutions): https://youtu.be/r9yvzd0tTJQ