Tara’s Beautiful Permutations – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Tara’s Beautiful Permutations HackerRank Solution
#include <bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
int dp[2001][2001][2];
int rec(int one, int two, int ban)
{
if(one==0 && two==0)
return 1;
int& ret=dp[one][two][ban];
if(ret!=-1)
return ret;
ret=0;
if(one>0)
ret=(ret+1LL*rec(one-1, two, 0)*(one-ban))%MOD;
if(two>0)
ret=(ret+1LL*rec(one+1, two-1, 1)*two)%MOD;
return ret;
}
int main()
{
memset(dp, -1, sizeof dp);
int Q;
scanf("%d", &Q);
while(Q--)
{
int N;
scanf("%d", &N);
map<int, int> m;
for(int i=0; i<N; i++)
{
int a;
scanf("%d", &a);
m[a]++;
}
int one=0, two=0;
for(auto& it: m)
{
if(it.second==1)
one++;
else
two++;
}
printf("%d\n", rec(one, two, 0));
}
return 0;
}
Java Tara’s Beautiful Permutations HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class C {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
for(int T = ni();T > 0;T--){
int n = ni();
int[] a = na(n);
Arrays.sort(a);
int[] fs = new int[3];
int f = 0;
for(int i = 0;i < n;i++){
if(i > 0 && a[i] == a[i-1]){
f++;
}else{
fs[f]++;
f = 1;
}
}
fs[f]++;
int mod = 1000000007;
long[][] pre = new long[2][fs[2]+1];
long[][] cur = new long[2][fs[2]+1];
pre[0][fs[2]] = 1;
for(int i = 0;i < n;i++){
for(int j = 0;j < 2;j++){
Arrays.fill(cur[j], 0L);
}
for(int j = 0;j <= fs[2];j++){
cur[0][j] += pre[0][j] * (n-i-j*2) + pre[1][j] * (n-i-j*2-1);
cur[0][j] %= mod;
if(j-1 >= 0){
cur[1][j-1] += (pre[0][j] + pre[1][j]) * j;
cur[1][j-1] %= mod;
}
}
long[][] dum = pre; pre = cur; cur = dum;
}
out.println((pre[0][0]+pre[1][0])%mod);
}
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new C().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private 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++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, 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();
}
}
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();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Tara’s Beautiful Permutations HackerRank Solution
# answer comes out to be [sum j=0 to k] ((-1)^j)*(kCj)*(m-j)!/2^(k-j)
# where
# n are the number of unique integ m is the length of array, permutation
# k=m-n number of repetitions
# kCj is selecting j out of k
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)
Python 2 Tara’s Beautiful Permutations HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
mod = 10**9+7
lim = 2000
pq = [[0 for i in xrange(lim+2)] for j in xrange(lim+2)]
pq[0][0] = 1
for p in xrange(lim+1):
for q in xrange(lim+1):
pq[p][q] += q * pq[p][q-1]
if(p != 0):
pq[p][q] += p *(pq[p-1][q+1] - pq[p-1][q])
pq[p][q] %= mod
Q = int(input())
for t in xrange(Q):
q = int(input())
arr = [int(x) for x in raw_input().split()]
arr.sort()
p = 0
for i in xrange(1,q+0):
if(arr[i] == arr[i-1]):
q -= 2
p+=1
print pq[p][q]
C Tara’s Beautiful Permutations HackerRank 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;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
