Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Tara's Beautiful Permutations Problem Solution

HackerRank Tara’s Beautiful Permutations Solution

Posted on July 2, 2023July 2, 2023 By Yashwant Parihar No Comments on HackerRank Tara’s Beautiful Permutations Solution

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

Table of Contents

  • Tara’s Beautiful Permutations C Solution
  • Tara’s Beautiful Permutations C++ Solution
  • Tara’s Beautiful Permutations C Sharp Solution
  • Tara’s Beautiful Permutations Java Solution
  • Tara’s Beautiful Permutations JavaScript Solution
  • Tara’s Beautiful Permutations Python 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 Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Cut Tree Problem Solution
Next Post: HackerRank Wet Shark and Two Subsequences

Related Posts

HackerRank Candies Problem Solution HackerRank Candies Problem Solution c
HackerRank Equalize the Array Problem Solution HackerRank Equalize the Array Problem Solution c
HackerRank Clique Problem Solution HackerRank Clique Problem Solution c
HackerRank Bill Division Problem Solution HackerRank Bill Division Problem Solution c
HackerRank Build a Palindrome Problem Solution HackerRank Build a Palindrome Problem Solution c
HackerRank Kingdom Connectivity Problem Solution HackerRank Kingdom Connectivity Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme