# Count Permutations | hackerearth solution

Problem

From a permutation $�$ of length $�$, Alice constructs an array $�$ of length $�$ such that ${�}_{�}=max\left({�}_{1},{�}_{2},\dots ,{�}_{�}\right)$. For example, if $�=\left[2,1,3,5,4\right]$, then Alice constructs the array $�=\left[2,2,3,5,5\right]$.

You are given an array $�$ containing $�$ integers. Find the number of permutations of length $�$ from which Alice can construct the given array $�$. Since the answer can be very large, print it modulo $\left({10}^{9}+7\right)$.

Input format

• The first line contains $�$ denoting the number of test cases. The description of $�$ test cases is as follows:
• For each test case:
• The first line contains a single integer $�$ denoting the size of array $�$.
• The second line contains $�$ integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$ denoting the elements of $�$.

Output format
For each test case, print the number of permutations, modulo $\left({10}^{9}+7\right)$ of length $�$ from which the given array $�$ can be constructed.

Constraints

$1\le �\le {10}^{4}\phantom{\rule{0ex}{0ex}}1\le �\le {10}^{5}\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}1\le {�}_{�}\le �\phantom{\rule{0ex}{0ex}}���\phantom{\rule{thickmathspace}{0ex}}��\phantom{\rule{thickmathspace}{0ex}}�\phantom{\rule{thickmathspace}{0ex}}����\phantom{\rule{thickmathspace}{0ex}}���\phantom{\rule{thickmathspace}{0ex}}����\phantom{\rule{thickmathspace}{0ex}}�����\phantom{\rule{thickmathspace}{0ex}}����\phantom{\rule{thickmathspace}{0ex}}���\phantom{\rule{thickmathspace}{0ex}}������\phantom{\rule{thickmathspace}{0ex}}3\cdot {10}^{5}.$

Sample Input
3
3
1 3 3
4
2 2 2 2
6
2 3 5 5 5 6


Sample Output
1
0
2

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Test case 1: The only permutation of length $3$ from which Alice can construct $�=\left[1,3,3\right]$ is $�=\left[1,3,2\right].$

Test case 2: There is no permutation of length of $4$ from which Alice can construct $�=\left[2,2,2,2\right].$

Test case 3: The permutations of length $6$ from which Alice can construct $�=\left[2,3,5,5,5,6\right]$ are

Code(JAVA):-

#include<bits/stdc++.h>
using namespace std;
{
long long s=0,k=1;
char c=getchar();
while(!isdigit(c))
{
k=(c=='-')?-1:1;
c=getchar();
}
while(isdigit(c))
{
s=s*10+c-'0';
c=getchar();
}
return s*k;
}
#define ll long long
#define Maxn 10010
#define Size 10010
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int main()
{
ll t=d;
while(t--)
{
ll n=d;
ll ans=1,tag=0,las=0;
for(int i=0;i<n;i++)
{
ll x=d;
if(x>las)
{
tag=x-las+tag-1;
las=x;
}
else if(x<las) ans=0;
else ans=ans*tag%1000000007,tag--;
}
printf("%lld\n",ans);
}
}

Code(JAVA):-

import java.io.*;
import java.util.*;
import java.math.BigInteger;
import java.util.stream.Collectors;
public class Main {
InputStream is;
PrintWriter out;
String INPUT = "";
void run() throws Exception {
is = System.in; out = new PrintWriter(System.out);
solve(); out.flush(); out.close();
}
public static void main(String[] args) throws Exception {
new Main().run();
}
public byte[] inbuf = new byte[1 << 16];
public int lenbuf = 0, ptrbuf = 0;
if (lenbuf == -1) {
throw new InputMismatchException();
}
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}
public boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
public int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}
public double nd() {
return Double.parseDouble(ns());
}
public char nc() {
return (char) skip();
}
private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) {
sb.appendCodePoint(b);
}
return sb.toString();
}
private int ni() {
return (int) nl();
}
private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
}
class Pair {
int first;
int second;
Pair(int a, int b) {
first = a;
second = b;
}
}
long[] nal(int n) {
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = nl();
}
return arr;
}
int N = 1000001;
long[] factorialNumInverse = new long[N + 1];
long[] naturalNumInverse = new long[N + 1];
long[] fact = new long[N + 1];
int mod = 1000000007;
void solve() {
int test_case = 1;
InverseofNumber();
InverseofFactorial();
factorial();
test_case = ni();
while (test_case-- > 0) {
go();
}
}
// WRITE CODE FROM HERE :-
void go() {
int n = ni();
int[] arr = new int[n];
Map<Integer, Integer> map = new TreeMap<>();
boolean f = false; long prev = 0;
for(int i=0; i<n; i++) {
arr[i] = ni();
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
if(i == 0) {
prev = arr[i];
continue;
}
if(arr[i] < prev) {
f = true;
}
prev = arr[i];
}
if(f) {
out.println(0);
return;
}
// now check if the number of occurence of particular number is correct or not. Lets see.
int pev = 0; f = false;
long ans = 1;
int cc = 0, p = 0;
for(Map.Entry<Integer, Integer> e : map.entrySet()) {
pev += e.getValue();
if(e.getValue() > e.getKey()) {
f = true;
break;
}
if(pev > e.getKey()) {
f = true;
break;
}
p = e.getKey()-1-cc;
cc += e.getValue();
ans = (ans * nCr(p, e.getValue() - 1)) % mod;
}
if(f) {
out.println(0);
return;
}
out.println(ans);
}
void InverseofNumber() {
naturalNumInverse[0] = naturalNumInverse[1] = 1;
for(int i = 2; i <= N; i++) {
naturalNumInverse[i] = naturalNumInverse[mod % i] * (long)(mod - mod / i) % mod;
}
}
void InverseofFactorial() {
factorialNumInverse[0] = factorialNumInverse[1] = 1;
for(int i = 2; i <= N; i++) {
factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % mod;
}
}
void factorial() {
fact[0] = 1;
for(int i = 1; i <= N; i++) {
fact[i] = (fact[i - 1] * (long)i) % mod;
}
}
long nCr(int N, int R) {
if(N < 0 || R < 0 || R > N) return 0L;
long ans = ((fact[N]) % mod * factorialNumInverse[N - R]) % mod;
return ans;
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-