HackerRank Tara’s Beautiful Permutations problem solution YASH PAL, 31 July 2024 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("%un",r); } return 0; } {“mode”:”full”,”isActive”:false} algorithm coding problems