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:
- The first line contains an integer, n. denoting the number of elements in array A.
- 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
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)
