Cards Permutation – 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++ Cards Permutation HackerRank Solution
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <cstring>
using namespace std;
const int kMaxN = 3e5+5, kMod = 1e9+7;
int fact[kMaxN], inv_fact[kMaxN];
int num_constant_ft[kMaxN], num_wildcard_ft[kMaxN];
int n;
void Update(int aib[], int pos, int val) {
while (pos <= n) {
aib[pos] += val;
pos += pos & (-pos);
}
}
int Query(int aib[], int pos) {
int r = 0;
while (pos) {
r += aib[pos];
pos -= pos & (-pos);
}
return r;
}
int& Mod(int& a) {
if (a >= kMod) {
return a -= kMod;
}
return a;
}
int Pow(int a, int p) {
int r = 1;
while (p) {
if (p & 1) {
r = 1LL * r * a % kMod;
}
a = 1LL * a * a % kMod;
p /= 2;
}
return r;
}
void Init(int n) {
fact[0] = inv_fact[1] = 1;
for (int i = 1; i <= n; i += 1) {
fact[i] = 1LL * fact[i - 1] * i % kMod;
}
inv_fact[n] = Pow(fact[n], kMod - 2);
for (int i = n - 1; i; i -= 1) {
inv_fact[i] = 1LL * inv_fact[i + 1] * (i + 1) % kMod;
}
}
int main() {
cin >> n;
Init(n);
vector<int> v(n);
for (auto& itr : v) {
cin >> itr;
}
int num_wildcard = 0;
map<int, int> is_present;
for (int i = 1; i <= n; i += 1) {
is_present[i] = false;
}
for (auto itr : v) {
num_wildcard += (itr == 0);
if (itr) {
is_present[itr] = true;
}
}
vector<int> wildcard_values = {};
for (auto itr : is_present) {
if (itr.second == 0) {
wildcard_values.push_back(itr.first);
}
}
int answer = 0;
int num_wildcards_right = 0;
int num_wildcard_constant = 0;
for (auto itr : wildcard_values) {
Update(num_wildcard_ft, itr, +1);
}
for (int i = n - 1; i >= 0; i -= 1) {
int f = fact[n - i - 1];
if (v[i] == 0) {
// wildcard wildcard
if (num_wildcard > 1) {
Mod(answer += 1LL * f * ((1LL * num_wildcard * (num_wildcard - 1) / 2) % kMod) % kMod * num_wildcards_right % kMod * fact[num_wildcard - 2] % kMod);
}
// wildcard constant
if (num_wildcard) {
Mod(answer += 1LL * f * num_wildcard_constant % kMod * fact[num_wildcard - 1] % kMod);
}
num_wildcards_right += 1;
} else {
Mod(num_wildcard_constant += num_wildcard - Query(num_wildcard_ft, v[i]));
// constant wildcard
if (num_wildcard) {
Mod(answer += 1LL * f * num_wildcards_right % kMod * Query(num_wildcard_ft, v[i]) % kMod * fact[num_wildcard - 1] % kMod);
}
// constant constant
Mod(answer += 1LL * f * Query(num_constant_ft, v[i]) % kMod * fact[num_wildcard] % kMod);
Update(num_constant_ft, v[i], +1);
}
}
Mod(answer += fact[num_wildcard]);
cout << answer << '\n';
}
Java Cards Permutation HackerRank Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
private static final int modulus = 1000000007;
private static int[] knowns; // known numbers, (input order)
private static int[] gkArr; // gkArr[k] number of knowns after k in x s.t k>i_i
private static int[] guArr; // guArr[k] number of unknowns s.t. k>u
private static int[] remainingUnknownsArr;// number of unknowns in x[n-1-i:x.length]
private static long[] factorials; // factorials[i] = i! % modulus
private static long[] runningDiffs; // sum over remaining k of (U.len-guArr)
private static long[] EO; // Expected ordinals
//O(n+klgk) sum = |U|!(1+sum over n of n!*EO_n) % modulus
static long solve(int[] x) { //O(n + klgk)
int n = x.length;
long sum = 1L;
factorialsInit(n); //O(n)
int[] U = getUnknownInts(n, x); //O(n) - relies on x
knownsInit(x); //O(n) - relies on x
gkInit(n); //O(klgk) - relies on knowns, x
guInit(n, U); //O(n) - relies on unknowns, x
unknownsRemainingInit(x); //O(n) -relies on x
runningDiffsInit(x, U); //O(n) -relies on gu, x
EOInit(x, n, U); //O(n) - relies on knowns, unknowns, gk, gu, running sums, x
for(int i = 1; i < n; i++) //O(n)
sum = addMod(sum, mulMod(EO[i], factorials[i]));
sum = mulMod(sum, factorials[U.length]);
return sum;
}
//O(klgk) setup GOOD
private static void gkInit(int n) {
gkArr = new int[n+1];
int[][] arrs = new int[2][knowns.length];
arrs[0] = Arrays.copyOfRange(knowns, 0, knowns.length);
int subLen = 1;
int b = 0;
do {
int i = 0;
subLen *= 2;
int j = (subLen >>> 1);
int endSub = subLen;
int counter = 0;
int imin = Math.min(knowns.length, endSub - (subLen>>>1));
int jmin = Math.min(knowns.length, endSub);
while(counter < knowns.length) {
if(j < jmin && i < imin && arrs[b][i] < arrs[b][j]) {
arrs[(b+1)%2][counter] = arrs[b][i];
gkArr[arrs[b][i]] += Math.max(0, (counter++)-i++);
} else if(j < jmin) {
arrs[(b+1)%2][counter] = arrs[b][j];
gkArr[arrs[b][j]] += Math.max(0, (counter++)-j++);
} else if(i < imin) {
arrs[(b+1)%2][counter] = arrs[b][i];
gkArr[arrs[b][i]] += Math.max(0, (counter++)-i++);
} else {
endSub += subLen;
i = j;
j += (subLen>>>1);
imin = Math.min(knowns.length, endSub - (subLen>>>1));
jmin = Math.min(knowns.length, endSub);
}
}
b = (b+1)%2;
} while (subLen < knowns.length);
}
//O(n) setup
private static void runningDiffsInit(int[] x, int[] U) { //Sum over k of U_g
runningDiffs = new long[x.length];
runningDiffs[0] = (x[x.length-1] == 0) ? 0 : U.length - guArr[x[x.length-1]];
for(int i = 1; i < x.length; i++) {
if(x[x.length-1-i] != 0)
runningDiffs[i] = U.length - guArr[x[x.length-1-i]];
runningDiffs[i] = addMod(runningDiffs[i], runningDiffs[i-1]);
}
}
//O(n) setup GOOD
private static void unknownsRemainingInit(int[] x) {
remainingUnknownsArr = new int[x.length];
int u = 0;
for(int i = x.length-1; i >= 0; i--)
remainingUnknownsArr[i] = (x[i] == 0) ? u++ : u; //INCLUSIVE
}
//O(n) setup GOOD
private static void guInit(int n, int[] U) {
guArr = new int[n+1];
int k = 0;
int u = 0;
for(int i = 0; i < U.length; i++) {
while( k <= U[i])
guArr[k++] = u;
u++;
}
while( k < guArr.length)
guArr[k++] = u;
}
//O(n) setup
private static void EOInit(int[] x, int n , int[] U) {
EO = new long[x.length];
long d = 0L;
long invertedUlen = binaryExpMod(U.length, Solution.modulus-2L);
for(int i = 1; i < n; i++) {
if(x[n-1-i] == 0) {
//from unknown perms
EO[i] = mulMod(remainingUnknownsArr[n-1-i], 500000004L); // div by 2
//from knowns DP
d = mulMod(runningDiffs[i], invertedUlen);
EO[i] = addMod(EO[i], d);
} else {
//fraction of unknowns larger
d = mulMod(guArr[x[n-1-i]], invertedUlen);
EO[i] = addMod(EO[i], mulMod(remainingUnknownsArr[n-1-i], d));
//number of knowns larger
EO[i] = addMod(EO[i], gkArr[x[n-1-i]]);
}
}
}
//O(lgn) GOOD
private static long binaryExpMod(long l, long pow) { //l^(modulus-2) mod modulus
if (l == 0L && pow != 0L)
return 0L;
long[] squares = new long[30]; //30 = ciel(lg(modulus-2)) > ciel(lg(n))
squares[0] = l % Solution.modulus;
for(int i = 1; i < 30; i++)
squares[i] = mulMod(squares[i-1], squares[i-1]);
long result = 1L;
int i = 0;
while(pow != 0L) {
if((pow & 1L) == 1L)
result = mulMod(result, squares[i]);
i++;
pow >>>= 1;
}
return result;
}
//O(n) setup
private static void factorialsInit(int n) {
factorials = new long[n+1];
factorials[0] = 1L;
factorials[1] = 1L;
for(int i = 2; i <= n; i++)
factorials[i] = Solution.mulMod(factorials[i-1], i);
}
//O(1) GOOD
private static long mulMod(long result, long l) {
return ( (result%Solution.modulus) * (l%Solution.modulus) )%Solution.modulus;
}
//O(1) GOOD
private static long addMod(long result, long l) {
return ( (result%Solution.modulus) + (l%Solution.modulus) )%Solution.modulus;
}
//O(n) setup GOOD
private static int[] getUnknownInts(int n, int[] x) { //O(n) but setup so insignif
int[] ints = new int[n];
for(int i = 1; i <= n; i++)
ints[i-1] = i;
for(int i: x)
if(i != 0) {
ints[i-1] = 0;
n--;
}
int[] intsOut = new int[n];
n = 0; //becomes index
for(int i: ints)
if(i != 0)
intsOut[n++] = i;
return intsOut;
}
//O(n) setup GOOD
private static void knownsInit(int[] x) {
int counter = 0;
for(int a: x)
if(a > 0)
counter++;
knowns = new int[counter];
counter = 0;
for(int a: x)
if(a > 0)
knowns[counter++] = a;
}
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 n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
int[] a = new int[n];
String[] aItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < n; i++) {
int aItem = Integer.parseInt(aItems[i]);
a[i] = aItem;
}
long result = solve(a);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
Python 3 Cards Permutation HackerRank Solution
import math
import os
import random
import re
import sys
from bisect import bisect , insort
N = pow(10,9)+7
def update(bit, i, v):
n = len(bit)
while i < n :
bit[i]+=v
i+=i&(-i)
def getsum(bit, i):
s=0
while i>0 :
s+=bit[i]
i -= i&(-i)
return s
def getnP(P,fixed):
n = len(P)
m = max(P)
nI=[0]
for i in range(2,n+1):
nI.append(nI[-1] + fixed[i-2] )
bit = [0 for i in range(m+1)]
nP = [0 for i in range(n)]
for i in range(n-1,-1,-1):
if P[i] > 0 :
nP[i] = nI[P[i]-1] - getsum(bit, P[i]-1)
update(bit, P[i], 1)
else :
nP[i] = -1
nP[0] = 0
return nP
def solve(P):
n = len(P)
fixed = n*[0]
for v in P:
if v > 0 :
fixed[v-1] = 1
idZ = [i for i in range(n) if P[i]==0 ]
idNZ = [i for i in range(n) if P[i]>0 ]
vP = [i for i in range(1,n+1) if not fixed[i-1]]
nz = len(idZ)
nV,nZ,f = [0],[0],[1]
for i in range(1,n):
f.append( f[-1]*i %N )
nV.append(nV[-1]+(not fixed[i-1]))
nZ.append(nZ[-1]+(not P[i-1]))
f.append( f[-1]*n %N)
nP = getnP(P,fixed)
Tnz = sum( ( P[i] - 1 - nP[i] ) * f[n-i-1] for i in idNZ )
Tz = sum( ( i - nZ[i] ) * f[n-i-1] for i in idZ )
S = f[nz] * ( Tnz - Tz + 1) %N
if nz > 0 :
svP = sum(j-1 for j in vP)
snPV = [0]
for i in range(1,n):
snPV.append( snPV[-1] + nV[P[i-1]-1]*(P[i-1]>0) )
Tnz = sum( nZ[i] * nV[P[i]-1] * f[n-i-1] for i in idNZ )
Tz = sum( ( svP + snPV[i] ) * f[n-i-1] for i in idZ )
S += f[nz-1] * ( Tz - Tnz ) %N
if nz > 1 :
Tz = sum( nZ[i] * f[n-i-1] for i in idZ ) * sum( nV[l-1] for l in vP if l>1 )
S -= f[nz-2] * Tz %N
return S%N
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
a = list(map(int, input().rstrip().split()))
result = solve(a)
fptr.write(str(result) + '\n')
fptr.close()
Python 2 Cards Permutation HackerRank Solution
#!/bin/python
import math
import os
import random
import re
import sys
# Complete the solve function below.
MAXN = 3e5 + 5
mod = int(1e9 + 7)
inv2 = (mod + 1) >> 1
c = []
pre = []
fac = []
N = 0
count = 0
lex = 0
def add(a, b):
a += b
return a - mod if a >= mod else a
def pop(a, b):
a -= b
return a + mod if a < 0 else a
def mul(a, b):
return (a * b) % mod
def lowbit(i):
return i & (-i)
def update(o, v):
i = o + 1
while i <= N:
c[i] += v
i += lowbit(i)
def calc(o):
sum = 0
i = o + 1
while i >= 1:
sum += c[i]
i -= lowbit(i)
return sum
def prepare():
global count, lex
for i in range(1, N + 1):
a[i] -= 1
count += 1 if (a[i] == -1) else 0
if a[i] >= 0:
pre[a[i]] = 1
fac[0] = 1
for i in range(1, N + 1):
fac[i] = mul(i, fac[i - 1])
for i in range(1, N):
pre[i] += pre[i - 1]
lex = mul(mul(N, pop(N, 1)), inv2)
for i in range(1, N + 1):
if a[i] != -1:
lex = pop(lex, a[i])
# print('prep done:')
# print('a: {}'.format(a))
# print('pre: {}'.format(pre))
# print('fac: {}'.format(fac))
# print('lex: {}'.format(lex))
# print('count: {}'.format(count))
def cal2(n):
return mul(mul(n, pop(n, 1)), inv2)
def solve(x):
global count, lex
prepare()
cur = 0
ans = 0
for i in range(1, N + 1):
if a[i] != -1:
sum = mul(fac[count], a[i] - calc(a[i]))
if count >= 1:
sum = pop(sum, mul(fac[count - 1],
mul(cur, a[i] + 1 - pre[a[i]])))
sum = mul(sum, fac[N - i])
ans = add(ans, sum)
update(a[i], 1)
lex = pop(lex, pop(N - 1 - a[i], pop(pre[N-1], pre[a[i]])))
else:
sum = mul(lex, fac[count - 1])
if count >= 2:
sum = pop(sum, mul(fac[count - 2], mul(cur, cal2(count))))
sum = mul(sum, fac[N - i])
ans = add(ans, sum)
cur += 1
return add(ans, fac[count])
if __name__ == '__main__':
N = int(raw_input())
a = map(int, raw_input().rstrip().split())
a.insert(0, 0)
for i in range(len(a)):
pre.append(0)
fac.append(0)
c.append(0)
result = solve(a)
print(result)
C Cards Permutation HackerRank Solution
#include<stdio.h>
int n, a[300100], pos[300100],
mod = 1e9 + 7, occ[300100],
les[300100], grt[300100], st[300100],
lst[300100], gst[300100], bitree[300050];
void add(int idx, int val)
{
while( idx <= n )
{
bitree[idx] += val;
idx += ( idx & -idx );
}
}
int get(int idx)
{
int ans = 0;
while( idx > 0 )
{
ans += bitree[idx];
idx -= ( idx & -idx );
}
return ans;
}
long long fact[300100], factsumfr[300100], ans = 0;
long long pwr(long long a, long long b)
{
if( b == 0 )
{
return 1ll;
}
long long temp = pwr(a, b/2);
temp = ( temp * temp ) % mod;
if( b & 1 )
{
temp = ( temp * a ) % mod;
}
return temp;
}
long long inv(long long a)
{
return pwr(a, mod-2);
}
int main()
{
int i;
scanf("%d", &n);
for( i = 1 ; i <= n ; i++ )
{
scanf("%d", &a[i]);
pos[a[i]] = i;
if(a[i])
{
st[a[i]] = 1;
}
if(a[i])
{
occ[i] = 1;
}
}
fact[0] = 1;
for( i = 1 ; i <= n ; i++ )
{
les[i] = les[i-1] + occ[i], lst[i] =
lst[i-1] + st[i], fact[i] = ( fact[i-1] * i ) % mod;
}
for( i = n ; i >= 1 ; i-- )
{
grt[i] = grt[i+1] + occ[i], gst[i] = gst[i+1] + st[i];
}
int k = les[n];
long long faci = fact[n-k],
faci1 = fact[n-k-1], sumfrfr = 0;
for( i = 1 ; i <= n ; i++ )
{
if( a[i] == 0 )
{
sumfrfr = ( sumfrfr + ( ( fact[n-i] * (
n - i - grt[i+1] ) ) % mod * inv(n-k-1) ) % mod ) % mod;
factsumfr[i] = (
factsumfr[i-1] + fact[n-i] ) % mod;
}
else
{
factsumfr[i] = factsumfr[i-1];
}
}
for( i = 1 ; i <= n ; i++ )
{
long long inc = 0;
if( st[i] == 0 )
{
inc += ( inc + ( ( sumfrfr * ( i - 1 - lst[i] )
) % mod * fact[n-k-1] ) % mod ) % mod;
}
else
{
inc = ( inc + ( ( ( n - i + 1 - gst[i] )
* factsumfr[pos[i]] ) % mod * fact[n-k-1] )
% mod ) % mod;
inc = ( inc + ( ( ( ( ( i - lst[i] )
* fact[n-pos[i]] ) % mod * fact[n-k] ) % mod * (
n - pos[i] + 1 - grt[pos[i]] ) ) % mod
* inv(n-k) ) % mod ) % mod;
add(pos[i], 1);
int inv1 = get(n) - get(pos[i]);
inc = ( inc + ( ( fact[n-pos[i]]
* fact[n-k] ) % mod * inv1 ) % mod ) % mod;
}
ans = ( ans + inc ) % mod;
}
ans = ( ans + fact[n-k] ) % mod;
printf("%lld\n", ans);
return 0;
}