Header Ads Widget

Count Permutations | hackerearth solution

Rajnish Tripathi 21:23

 Problem

From a permutation � of length �, Alice constructs an array � of length � such that ��=max(�1,�2,…,��). For example, if �=[2,1,3,5,4], then Alice constructs the array �=[2,2,3,5,5].

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 (109+7).

 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,…,�� denoting the elements of �.

Output format
For each test case, print the number of permutations, modulo (109+7) of length � from which the given array � can be constructed.

Constraints

1≤�≤1041≤�≤1051≤��≤������������������������������������3⋅105.

 

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 �=[1,3,3] is �=[1,3,2].

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

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

 �=[2,3,4,5,4,1,6],�=[2,3,4,5,1,4,6]



Code(JAVA):-


#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
    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 d read()
#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;
public int readByte() {
if (lenbuf == -1) {
throw new InputMismatchException();
}
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read(inbuf);
} 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);
b = readByte();
}
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;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments