DAY7 - CRACK-A-CODE 2.0 Editorial

editorial
,
1

PROBLEM LINK:

Contest
Practice

Setter & Editorialist: Mayuresh Patle
Tester: Uttkarsh Bawankar

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Probability

PROBLEM:

For any given range [L,R], find the probability that a randombly selected integer in this range will be divisible by 7.

EXPLANATION:

Solution will be: \frac{Number \ of multiple s\ of \ 7 \ in\ given \ range}{Total \ integers\ in \ given \ range}

We know that total integers in given range [L , R] = R - L + 1

The only task that remains is to calculate the number of multiples of 7 in given range efficiently.

Hint 1

Number of multiples of 7 in range [1,N] = \lfloor\frac{N}{7}\rfloor

Hint 2

Number of multiples of 7 in range [L,R]
= Number\ of\ multiples\ in\ range \ [1,R] - Number\ of\ multiples\ in\ range\ [1,L-1]

Final Expression

Required Probability = \frac{\lfloor{\frac{R}{7}\rfloor} - \lfloor{\frac{L - 1}{7}\rfloor}}{R - L + 1}

Time Complexity: O(1) for each testcase.

SOLUTIONS:

Setter's Python Solution 
for _ in range(int(input())):
	l,r=map(int,input().split())
	t=r-l+1
	print("%.8f"%((r//7-(l-1)//7)/t))
Tester's C++ Solution 
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long t,l,r;
	double sampleSpace, favorable, probability;
	cin>>t;
	while(t--)
	{
		cin>>l>>r;
		favorable = (r/7) - (l-1)/7;
		sampleSpace = r-l+1;
		probability = favorable / sampleSpace;
		cout<<fixed<<setprecision(6)<<probability<<"\n";
	}	
    return 0;
}
1 Like