HackerRank Tara's Beautiful Permutations problem solution

In this HackerRank Tara's Beautiful Permutations problem solution You are given Q queries where each query consists of some array A. For each A, help Tara count the number of possible beautiful permutations of the n integers in A and print the count, modulo 10 to power 9 plus 7, on a new line.

Problem solution in Python.

factorial=[1,]
for i in range(1,2001):
    factorial.append(factorial[-1]*i)

pascal=[[0 for y in range(1001)] for x in range(1001)]

for i in range(1001):
    pascal[i][0]=1
    for j in range(1,i+1):
        pascal[i][j]=pascal[i-1][j-1]+pascal[i-1][j]
        
#print(factorial)
        
for _ in range(int(input())):
    m=int(input())
    n=len(set(input().split()))
    k=m-n
    
    ans=0
    f=1
    for j in range(0,k+1):

        kCj=pascal[k][j]
        ans+=f*kCj*factorial[m-j]//(2**(k-j))
        f=f*-1
    print(ans%1000000007)

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the beautifulPermutations function below.
     */
    static int beautifulPermutations(int[] arr) {
        /*
         * Write your code here.
         */
         HashSet<Integer> used = new HashSet<Integer>();
         int n = arr.length;
        for(int i = 0; i < n; i++)
            used.add(arr[i]);
        int k = n-used.size();
        long start = (long)1;
        long[][] dp = new long[n+1][k+1];
        for(int i = 1; i <= n; i++){
            start = (i*start)%1000000007;
            dp[i][0] = start;
        }
        for(int i = 1; i < k+1; i++){
            for(int j = 2*i; j < n+1; j++){
                long val = dp[j][i-1];
                if(dp[j][i-1] % 2 == 1)
                    val = dp[j][i-1] + 1000000007;
                dp[j][i] = (-dp[j-1][i-1] + val/2+1000000007)%1000000007;
            }
        }
        return (int)dp[n][k];
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            int arrCount = Integer.parseInt(scanner.nextLine().trim());

            int[] arr = new int[arrCount];

            String[] arrItems = scanner.nextLine().split(" ");

            for (int arrItr = 0; arrItr < arrCount; arrItr++) {
                int arrItem = Integer.parseInt(arrItems[arrItr].trim());
                arr[arrItr] = arrItem;
            }

            int result = beautifulPermutations(arr);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

{"mode":"full","isActive":false}

Problem solution in C++.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<vector<ll> > mat;

ll m=1e9+7,f[200005],inv[200005];

ll p(ll a,ll b)
{
    ll r=1;
    while(b)
    {
        if(b&1)
        r=(r*a)%m;
        a=(a*a)%m;
        b/=2;
    }
    return r;
}

ll ncr(ll n,ll r)
{
    if(r>n||r<0)
    return 0;
    ll k=(inv[r]*inv[n-r])%m;
    k=(f[n]*k)%m;
    return k;
}

int main()
{ios_base::sync_with_stdio(false);
int t;
gl(t);

f[0]=1;
rep(i,1,200004)
f[i]=(f[i-1]*i)%m;
inv[200004]=p(f[200004],m-2);
ren(i,200003,0)
inv[i]=(inv[i+1]*(i+1))%m;

ll in=p(2,m-2);
while(t--)
{
    int n;
    cin>>n;
    map<int,int> m1;
    rep(i,1,n)
    {
        int x;
        cin>>x;
        m1[x]++;
    }
    int c=0;
    tr(m1,it)
    {
        if(it->ss==2)
        c++;
    }
    ll ans=0;
    rep(i,0,c)
    {
        ll sgn=1;
        if(i%2==1)sgn=-1;
        ll x=(ncr(c,i)*f[n-i])%m;
        x=(x*p(in,c-i))%m;
        //ol(x);on;
        ans=(ans+sgn*x)%m;
        if(ans<0)ans+=m;
    }
    ol(ans);on;
}
return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#include<stdio.h>
#include<stdlib.h>
#define m 1000000007u
#define m2 500000004u
typedef long long unsigned llu;
typedef unsigned u;
int S(const void*x,const void*y){return*(int*)x-*(int*)y;}
u C[2222][2222],A[2222],F[2222];
u P(u b,u e)
{
    u r=1;
    for(;e;e>>=1)
    {
        if(e&1)r=r*(llu)b%m;
        b=b*(llu)b%m;
    }
    return r;
}
int main()
{
    u t,n,i,j,k,d,r;
    for(i=-1;++i<2222;)for(C[i][j=0]=1;j++<i;)
    if((C[i][j]=C[i-1][j-1]+C[i-1][j])>=m)C[i][j]-=m;
    for(F[i=0]=1;++i<2222;)F[i]=i*(llu)F[i-1]%m;
    for(scanf("%u",&t);t--;)
    {
        scanf("%u",&n);
        for(i=-1;++i<n;)scanf("%u",A+i);
        qsort(A,n,sizeof(u),S);
        for(i=d=0;++i<n;)d+=A[i]==A[i-1];
        k=P(m2,d);r=0;
        for(i=-1;++i<=d;)
        {
            j=C[d][i]*(llu)F[n-i]%m*(llu)k%m;
            if((k<<=1)>=m)k-=m;
            if(i&1)
            {
                if((r-=j)>m)r+=m;
            }
            else 
            {
                if((r+=j)>=m)r-=m;
            }
        }
        printf("%u\n",r);
    }
    return 0;
}

{"mode":"full","isActive":false}