HackerRank Tara’s Beautiful Permutations Solution

Yashwant Parihar,

In this post, we will solve HackerRank Tara’s Beautiful Permutations Problem Solution.

Tara has an array, A, consisting of n integers where each integer occurs at most 2 times in
the array.
Let’s define P to be a permutation of A where p, is the ith element of permutation P. Tara thinks a permutation is beautiful if there is no index & such that p; – P+1 = 0 where
i [0,n-1).
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 109 +7, on a new line.
Note: Two permutations, P and Q. are considered to be different if and only if there exists an index i such that p, q, and i € [0, n).
Input Format
The first line contains a single integer, q, denoting the number of queries. The 2. q subsequent lines describe each query in the following form:

  1. The first line contains an integer, n. denoting the number of elements in array A.
  2. The second line contains n space-separated integers describing the respective values of
    a0, a1,…,an-1 in array A.

Output Format

For each query, print the the number of possible beautiful permutations, modulo 10 power 9, on a new line.

Sample Input 0

3
3
1 1 2
2
1 2
4
1 2 2 1

Sample Output 0

1
2
2
HackerRank Tara's Beautiful Permutations Problem Solution
HackerRank Tara’s Beautiful Permutations Problem Solution

Tara’s Beautiful Permutations C Solution

#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;
}

Tara’s Beautiful Permutations C++ Solution

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef unsigned long long ull;

const int mod = 1e9 + 7;
int dp[2001][1001][2];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int ile_t; cin >> ile_t;
	while ( ile_t-- )
	{	
		map< int, int > M;
		int ile; cin >> ile;
		int h = 0, p = 0;
		for ( int i = 0; i < ile; ++i )
		{
			int pe; cin >> pe;
			if ( M[pe] )
				++h, --p;
			else 
				++M[pe], ++p;
		}
		dp[0][0][0] = 1;
		for ( int i = 1; i <= ile; ++i )
			for ( int k = 0; k <= h; ++k )
			{
				dp[i][k][0] = ( (ull)dp[i - 1][k][0] * ( p + k - ( i - 1 - k ) ) + (ull)dp[i - 1][k][1] * ( p + k - ( i - 1 - k ) - 1 ) ) % mod;
				if ( k > 0 )
					dp[i][k][1] = ( (ull)dp[i - 1][k - 1][0] * ( h - ( k - 1 ) ) + (ull)dp[i - 1][k - 1][1] * ( h - ( k - 1 ) ) ) % mod; 
			}
		cout << dp[ile][h][0] << '\n';
	}
}

Tara’s Beautiful Permutations C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;

public static class Factorial {
      public static long compute(int n) {
         long res = 1;
         while (n != 1) {
            res = res * n;
            n = n - 1;
         }
         return res;
      }
    }

class Solution {

    /*
     * Complete the beautifulPermutations function below.
     */
           static int beautifulPermutations(int[] arr)
        {
            int P = 0;
            var N = arr.Length;
            var dict = new Dictionary<int, int>();
            foreach (var num in arr)
            {
                if (!dict.ContainsKey(num))
                {
                    dict.Add(num, 0);
                }
                dict[num]++;
                if (dict[num] > 1) P++;
            }

            BigInteger[] factorialsP = calculateFactorialsP(P);
            var total = fact(N) / new BigInteger( Math.Pow(2, P));
            var ugly = calculateUgly(P, N, factorialsP);
            var beautiful = total - ugly;

            return (int) ((beautiful) % (1000000000 + 7));
        }

        private static BigInteger[] calculateFactorialsP(int P)
        {
            BigInteger[] result = new BigInteger[P+1];
            result[0] = 1;
            for (int ii = 1; ii <= P; ii++)
            {
                result[ii] = ii * result[ii - 1];
            }

            return result;
        }


        static BigInteger calculateUgly(int P, int N, BigInteger[] factorialsP)
        {
            BigInteger suma = 0;
            BigInteger[] result1 = new BigInteger[P];
            BigInteger[] tmp = new BigInteger[P];

            if (P > 0)
            {
                result1[0] = P * fact(N - 1) / new BigInteger(Math.Pow(2, P - 1));
            }
            else
            {
                return 0;
            }

            for (int k = 2; k <= P; k++)
            {
                result1[k - 1] = result1[k - 2] / k / (N - k + 1) * 2 * (P - k + 1);
            }

            for (int jj = 0; jj < P; jj+=2)
            {
                suma += result1[jj];
            }

            for (int jj = 1; jj < P; jj+=2)
            {
                suma -= result1[jj];
            }

          /*
         
            for (int ii = P - 2; ii >= 0; ii--)
            {
                for (int jj = P-1; jj > ii; jj--)
                {
                    result1[ii] = result1[ii] - 2 * result1[jj];// CombinatorianNumber(jj+1,ii+1, factorialsP ) * result1[jj];
                }
            }

            for (int jj = 0; jj < P; jj++)
            {
                suma += result1[jj];
            }
          */

            return suma;
        }

        public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n * fact(n - 1);


    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int t = Convert.ToInt32(Console.ReadLine());

        for (int tItr = 0; tItr < t; tItr++) {
            int arrCount = Convert.ToInt32(Console.ReadLine());

            int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), arrTemp => Convert.ToInt32(arrTemp))
            ;
            int result = beautifulPermutations(arr);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

Tara’s Beautiful Permutations Java Solution

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();
    }
}

Tara’s Beautiful Permutations JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

    const MODULO = 10**9 + 7


/*
 * Complete the beautifulPermutations function below.
 */
function beautifulPermutations(arr) {
    /*
     * Write your code here.
     */

/*
    arr.sort()

    //var count = {}
    var n = 0;
    var result = 1;
    var inSospeso = 0
    var last = -1;

    arr.forEach(v => {
        if(last !== v) {
            var possibleIndexOfInsert = n + 1
            result = (result * possibleIndexOfInsert) % MODULO

            if(inSospeso){
                // se ci sono in-sospeso, mettersi in mezzo ad ogni coppia
                result = result + inSospeso   

                // se ci sono in-sospeso, mi aggiungo in posti (non in mezzo)
                // e rimangono in sospeso
                inSospeso = inSospeso * n
            }

        }else{
            var newInSospeso = result // aggiungi valori consecutivi in tutti i result

            // no left or right of the equal element
            var possibleIndexOfInsert = n + 1 - 2
            result = (result * possibleIndexOfInsert) % MODULO

            if(inSospeso) {
                
            }

        }
        n++;
        last = v

        console.log('step ' + n + ' v: ' + v + 
        ' result: ' + result + ' inSospeso: ' + inSospeso)
    })

    return result
    */

    var count = {}
    var n = arr.length
    var double = 0;

    arr.forEach(v => {
        if(count[v]){
            double++;
        }
        count[v] = true
    })

    var single = n - double * 2;


    return f(single, double)
}

var cache = {}

function f(single, double, doNotRemoveTheSingleElementEqualTheLastRemoved = 0) {
    if(single === 1 && double === 0) {
        if(doNotRemoveTheSingleElementEqualTheLastRemoved) {
            return 0; // can't do... we have only one single, of course is 
            // equal to the last removed element!
        }
        return 1;
    }

    var key = single + '-' + double + '-' + doNotRemoveTheSingleElementEqualTheLastRemoved
    if(cache[key]) {
        return cache[key]
    }

    // for the recursion:
    // - we extract one element (random)
    // - that will be the first element in the permutation
    // - we call f recursivelly
    // - the result is n * f_recursive

    // we need to divide two cases 
    // 1) we remove a single 
    // n = number of single  
    var n_single = single - doNotRemoveTheSingleElementEqualTheLastRemoved  
    var r1 = n_single > 0 ? n_single * f(single-1, double, 0) : 0

    // 2) we remove a double
    // n = number of double
    var r2 = double > 0 ? double * f(single+1, double-1, 1) : 0

    var r = (r1 + r2) % MODULO

    cache[key] = r

    return r;
}


function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const arrCount = parseInt(readLine(), 10);

        const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));

        let result = beautifulPermutations(arr);

        ws.write(result + "\n");
    }

    ws.end();
}

Tara’s Beautiful Permutations Python Solution

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

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

for i in range(1001):
    permu[i][0]=1
    for j in range(1,i+1):
        permu[i][j]=permu[i-1][j-1]+permu[i-1][j]
        
        
for _ in range(int(input())):
    num=int(input())
    num1=len(set(input().split()))
    diff=num-num1
    
    final=0
    f=1
    for j in range(0,diff+1):

        permu1=permu[diff][j]
        final+=f*permu1*fact[num-j]//(2**(diff-j))
        f=f*-1
    print(final%1000000007)
c C# C++ HackerRank Solutions java javascript python