Median from first 3 element | DS-Algo | Maths

Question asked in DE Shaw

Given a number N.
Need to get all permutation of number from 1 to n.

Take first 3 elements.
pivot element as median from first 3 elements.

Given another number k.
x = Need to find that for a given number N, how many time k appears as pivot element.
Answer to given as x modulo 10^9 + 7



You can try yourself.
Approach is given below.





















Solution:

 small = Number smaller than k
large = Number larger than k
remaining = N - 3

ans = small*large*3!*remaining!

for factorial: may need to implement using Big Integer class

Check how to use BigInteger to divide,multiply