You are not logged in. Please login at www.codechef.com to post your questions!

×

NAICHEF - Editorial

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.

This question is marked "community wiki".

asked 06 Jun, 01:25

likecs's gravatar image

6★likecs
3.4k1356
accept rate: 9%

edited 12 Jun, 08:18


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

link

answered 13 Jun, 18:42

code_report's gravatar image

4★code_report
903
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,366
×1,410
×357
×201
×160
×6

question asked: 06 Jun, 01:25

question was seen: 233 times

last updated: 13 Jun, 18:42