Single Lane Highway | TCS Codevita 9 Solution Zone 2 2020

This post explains the TCS CodeVita problem Single Lane Highway step by step: the problem statement, input and output format, constraints, a sample test case and a working solution in Python that you can study and run.

Problem Description

Certain number of cars are passing a single lane road. Speeds of all cars vary. It is easy to see, that depending on the speeds of the cars various groups will be formed.

Being a single lane road passing/overtaking is not allowed. Given speeds of cars, calculate how many groups can be formed if all possible permutations are taken into account. Refer example1 for better understanding.

Print number of groups divided by the number of permutations.

Constraints

0 <= N < 10 ^ 5
0 <= speed of individual vehicle < 10 ^ 9

Input

First line contains an integer N, which denotes the number of vehicles
Second line contains N space separated integers which denotes the speed of individual vehicle.

Output

Print number of groups divided by the number of permutations rounded upto 6 decimal places.
Time Limit
1

Examples

Example 1

Input

3
10 20 30

Output

1.833333

Explanation

So all possible permutations are:
{10 20 30}
{10 30 20}
{20} {10 30}
{20 30} {10}
{30} {10 20}
{30 20} {10}
So here there are total 6 permutations, and total number of groups are 11.

So, output is 11/6 = 1.833333

Example 2

Input

4
56 78 13 92

Output

2.083333

Explanation

So here there are total 24 permutations,

For example

{56 78 13 92}
{92} {13 78 56}
{56} {13 92 78}
{78 92} {13 56}
.
.
So on and so forth. The total number of groups are 50.

So, the output is 50/24 = 2.083333

Single Lane Highway Solution in Python

from itertools import permutations
import math 
# def get_count(d):

#     c=0

#     for i in d:

#     c+=1 

#     return c 

n=int(input())

l=list(map(int,input().split()))

cc=[]

# d1=permutations(l,n-1)

# d2=permutations(l,n)

# cc.append(get_count(d1))

# cc.append(get_count(d2))

s1=math.factorial(n)//math.factorial(n-(n))

s2=math.factorial(n)//math.factorial(n-(n-1))

cc.append(s1)

cc.append(s2)

if(n%2==0):

    t=sum(cc)+2

else:

    t=sum(cc)-1 
print("%.6f"%(t/cc[-1]))

Recommended Codevita Problems
Count Pairs | TCS CodeVita 9 Solution ( Zone 1 ) 2020
Lift | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Number Distancing | TCS CodeVita 9 Solution ( Zone 1 ) 2020
Critical Planets | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Prime Time Again | TCS CodeVita 9 Solution ( Zone 1 ) 2020
Minimum Gifts | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Minimize The Sum | TCS CodeVita 9 Solution ( Zone 1 ) 2020
Railway Station | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Hedger | TCS CodeVita 9 Solution ( Zone 1 ) 2020
Codekart | TCS CodeVita 9 Solution ( Zone 1 ) 2020
If any queries You can mail to codinghumanshelp@gmail.com or comment down below

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More TCS CodeVita solutions All coding problems MCQ practice