# HackerRank Cards Permutation problem solution

In this HackerRank Cards Permutation problem solution, we have given the n integers from 1 to n. and we need to write all possible permutations in increasing lexicographical order and wrote each permutation in a new line. and we need to print a single line containing a single integer denoting the sum of the line numbers of the permutations which could possibly be the permutation.

## Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys
import itertools
#
# Complete the 'solve' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts INTEGER_ARRAY x as parameter.
#

class fenwick:
def __init__(self, n):
self.tree = [0]*(n+1)

def update(self, i):
# i is 0 based index
i += 1
while i < len(self.tree):
self.tree[i] += 1
i += i & (-i)

def query(self, i):
# i is 0 based index
sum = 0
i += 1
while i > 0:
sum += self.tree[i]
i -= i & (-i)
return sum

def solve(x):
n = len(x)
mod = 1000000007
missing = [True]*n
bit1 = fenwick(n)
bit2 = fenwick(n)
for i in range(n):
x[i] -= 1
if x[i] != -1:
missing[x[i]] = False
missisng_elems = []
for i in range(n):
if missing[i]:
missisng_elems.append(i)
missing_sum = 0
m = len(missisng_elems)
for i in missisng_elems:
missing_sum += i
if i < n-1:
bit2.update(i+1)
fact = [1]*500010
for i in range(1, 500010):
fact[i] = i*fact[i-1] % mod
total_cost = 0
p = 0
y = 0
for i in range(n-1):
if x[i] != -1:
if m == 0:
D1 = bit1.query(x[i])
bit1.update(x[i]+1)
cost = (x[i] - D1)*fact[n-i-1]
else:
D1 = bit1.query(x[i])*m
no_of_smaller_missing_elems = bit2.query(x[i])
D2 = no_of_smaller_missing_elems*p
# print('D1:{} D2:{}'.format(D1, D2))
bit1.update(x[i]+1)
cost = (x[i]*m - (D1 + D2))*fact[m-1]*fact[n-i-1]
y += m - no_of_smaller_missing_elems
else:
if p == 0:
cost = (missing_sum - y)*fact[m-1]*fact[n-i-1]
else:
D1 = p*m*(m-1)//2
D2 = y*(m-1)
cost = (missing_sum * (m-1) - (D1 + D2))*fact[m-2]*fact[n-i-1]
p += 1
# print('i:{}, x[i]:{}, cost:{}'.format(i, x[i], cost))
total_cost += cost % mod
return (total_cost + fact[m]) % mod

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

n = int(input().strip())

a = list(map(int, input().rstrip().split()))

result = solve(a)

fptr.write(str(result) + '\n')

fptr.close()

{"mode":"full","isActive":false}

## Problem solution in Java.

import java.io.IOException;
import java.util.*;

public class CardsPermutationFinal {
private final static long MOD = 1000000007;
private final static long INV_TWO = inverseElmnt(2);
private static final long Y_DISP = 10000000000l;
private static final Set<Long> USED_Y = new HashSet<>();

private static long pow(long n, long p) {
if (p == 0) {
return 1;
}

if (p % 2 == 0) {
return pow((n * n) % MOD, p / 2) % MOD;
} else {
return (n * pow(n, p - 1)) % MOD;
}
}

private static long inverseElmnt(long n) {
return pow(n, MOD - 2);
}

private static long fact(int n) {
long res = 1;
for(int i = 1; i <= n; i++) {
res = (res * i) % MOD;
}
return res;
}

private static long generateY() {
long y;
do {
y = (long)(Y_DISP * Math.random());
} while (USED_Y.contains(y));
return y;
}

private long run(int n, int[] perm) {
int[] undefinedAmnt = new int[n];
undefinedAmnt[n - 1] = 0;

for (int i = n - 2; i >= 0; i--) {
undefinedAmnt[i] = undefinedAmnt[i + 1] + (perm[i + 1] == 0 ? 1 : 0);
}

int totalUndef = undefinedAmnt[0] + (perm[0] == 0 ? 1 : 0);

long[] bin = new long[n];
bin[n - 1] = 1;
long chisl = totalUndef;
long znam = 1;

long[] incr = new long[n];
incr[n - 1] = 0;

long currentIncr = perm[n - 1] == 0 ? 1 : 0;

int chislForIncr = totalUndef - 1;
int znamForIncr = 1;

for (int i = n - 2; i >= 0; i--) {
if (undefinedAmnt[i] == undefinedAmnt[i + 1]) {
bin[i] = bin[i + 1];
} else {
bin[i] = (((bin[i + 1] * chisl) % MOD) * inverseElmnt(znam))% MOD;
chisl--;
znam++;
}

if (perm[i] != 0) {
incr[i] = perm[i + 1] != 0 ? incr[i + 1] : currentIncr;
} else {
if (0 == currentIncr) {
currentIncr = 1;
} else {
currentIncr = (((currentIncr * chislForIncr) % MOD) * inverseElmnt(znamForIncr)) % MOD;
chislForIncr--;
znamForIncr++;
}
}
}

long[] colSum = new long[n];
long[] rowSum = new long[n];

int cell = n - 1;
while (cell >= 0 && perm[cell] != 0) {
cell--;
}

if (cell >= 0) {
colSum[cell] = 1;
rowSum[cell] = totalUndef;
}

int chislColSum = totalUndef - 1;
int znamColSum = 1;

int chislRowSum = totalUndef - 1;
int znamRowSum = 2;

for (int i = cell - 1; i >= 0; i--) {
if (perm[i] == 0) {
colSum[i] = (((colSum[i + 1] * chislColSum) % MOD) * inverseElmnt(znamColSum)) % MOD;
chislColSum--;
znamColSum++;

rowSum[i] = (((rowSum[i + 1] * chislRowSum) % MOD) * inverseElmnt(znamRowSum)) % MOD;
chislRowSum--;
znamRowSum++;
} else {
colSum[i] = colSum[i + 1];
rowSum[i] = rowSum[i + 1];
}
}

int[] lessAmntLeft = new int[n + 1];

cell = n - 1;
while (cell >= 0 && perm[cell] == 0) {
cell--;
}

Treap t = null;
if (cell >= 0) {
t = new Treap(perm[cell], generateY(), null, null);
}

for (int i = cell - 1; i >= 0; i--) {
if (perm[i] != 0) {
Treap res = new Treap(perm[i], generateY(), null, null);

Treap[] splitRes = t.split(perm[i]);
lessAmntLeft[perm[i]] = splitRes[0] == null ? 0 : splitRes[0].size;

if (null != splitRes[0]) {
res = merge(splitRes[0], res);
}

if (null != splitRes[1]) {
res = merge(res, splitRes[1]);
}
t = res;
}
}

int[] defVals = new int[n - totalUndef];
int defValsSize = 0;

for (int i = 0; i < n; i++) {
if (perm[i] != 0) {
defVals[defValsSize] = perm[i];
defValsSize++;
}
}

Arrays.sort(defVals);

long[] greaterUndef = new long[n + 1];
long[] smallerDefined = new long[n + 1];
long totalSum = 0;

for (int i = 0; i < defValsSize; i++) {
int definedValue = defVals[i];
int greaterCnt = n - definedValue - (defValsSize - i - 1);
greaterUndef[definedValue] = greaterCnt;
totalSum = (totalSum + greaterCnt) % MOD;

smallerDefined[definedValue] = i;
}

long[] resultInpt = new long[n];

for (int i = n - 1; i >= 0; i--) {
if (perm[i] != 0) {
resultInpt[i] = (((incr[i] * (perm[i] - 1 - smallerDefined[perm[i]])) % MOD) +
(lessAmntLeft[perm[i]] * bin[i]) % MOD) % MOD;
}
}

int undef = totalUndef;
for (int i = 0; i < n; i++) {
if (perm[i] == 0) {
resultInpt[i] = (((((rowSum[i] * undef) % MOD) * (undef - 1)) % MOD) * INV_TWO) % MOD;
resultInpt[i] = (resultInpt[i] + (colSum[i] * totalSum) % MOD) % MOD;
undef--;
} else {
totalSum = (totalSum - greaterUndef[perm[i]] + MOD) % MOD;
}
}

int undefRight = undefinedAmnt[0];
int undefLeft = 0;

long rightFact = fact(undefRight);
long leftFact = 1;
resultInpt[0] = (resultInpt[0] * rightFact) % MOD;

for (int i = 1; i < n; i++) {
if (perm[i] == 0) {
rightFact = (rightFact * inverseElmnt(undefRight)) % MOD;
undefRight--;
}

if (perm[i - 1] == 0) {
undefLeft++;
leftFact = (leftFact * undefLeft) % MOD;
}

resultInpt[i] = (resultInpt[i] * ((rightFact * leftFact) % MOD)) % MOD;
}

long fact = 1;
int cnt = 1;

for (int i = n - 2; i >= 0; i--) {
resultInpt[i] = (resultInpt[i] * fact) % MOD;
cnt++;
fact = (fact * cnt) % MOD;
}

long result = fact(totalUndef);
for (int i = 0; i < n; i++) {
result = (result + resultInpt[i]) % MOD;
}

return result;
}

public static void main(String[] args) throws IOException {
int[] perm = new int[n];

for (int i = 0; i < n; i++) {
perm[i] = Integer.parseInt(permTkn.nextToken());
}

//Date start = new Date();
long res = new CardsPermutationFinal().run(n, perm);
//Date end = new Date();
//System.out.println(end.getTime() - start.getTime() + "ms");
System.out.println(res);
}

private static void recalculateSize(Treap t) {
if (null != t) {
t.recalculateSize();
}
}

public Treap merge(Treap l, Treap r) {
if (null == l) {
return r;
}

if (null == r) {
return l;
}

Treap res;

if (l.y > r.y) {
Treap newTreap = merge(l.right, r);
recalculateSize(newTreap);
res = new Treap(l.x, l.y, l.left, newTreap);
} else {
Treap newTreap = merge(l, r.left);
recalculateSize(newTreap);
res = new Treap(r.x, r.y, newTreap, r.right);
}

recalculateSize(res);
return res;
}

private class Treap {
private int x;
private long y;

private Treap left;
private Treap right;

private int size;

public Treap(final int x, final long y, final Treap left, final Treap right) {
this.x = x;
this.y = y;
this.right = right;
this.left = left;
}

private void recalculateSize() {
size = (null == left ? 0 : left.size) + (null == right ? 0 : right.size) + 1;
}

public Treap[] split(int x) {
Treap newLeft = null;
Treap newRight = null;

if (x < this.x) {

if (this.left == null) {
newRight = new Treap(this.x, this.y, this.left, this.right);
} else {
Treap[] splitResult = this.left.split(x);
newLeft = splitResult[0];
newRight = new Treap(this.x, this.y, splitResult[1], this.right);
}
} else {
if (this.right == null) {
newLeft = new Treap(this.x, this.y, this.left, this.right);
} else {
Treap[] splitResult = this.right.split(x);
newLeft = new Treap(this.x, this.y, this.left, splitResult[0]);
newRight = splitResult[1];
}
}

CardsPermutationFinal.recalculateSize(newLeft);
CardsPermutationFinal.recalculateSize(newRight);

return new Treap[]{newLeft, newRight};
}
}
}

{"mode":"full","isActive":false}

## Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cmax(a,b)        a = ((a) > (b) ? (a) : (b))
#define cmin(a,b)        a = ((a) < (b) ? (a) : (b))
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pii            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MAXN = 3e5 + 5;
const int oo = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) >> 1;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

int N, a[MAXN], fac[MAXN], pre[MAXN], cnt = 0, ans = 0, cur = 0, lex = 0;

namespace BIT{
int c[MAXN];
inline int lowbit(int i){return i & (-i);}
inline void upd(int o, int v){
for (int i = o + 1; i <= N; i += lowbit(i)) c[i] += v;
}
inline int calc(int o){
int sum = 0;
for (int i = o + 1; i >= 1; i -= lowbit(i)) sum += c[i];
return sum;
}
}using namespace BIT;

namespace solution{
int cal2(int n){return mul(mul(n, pop(n, 1)), inv2);}
void Prepare(){
scanf("%d", &N);
up (i, 1, N) scanf("%d", &a[i]);
up (i, 1, N) {
a[i]--;
cnt += (a[i] == -1);
if (a[i] >= 0) pre[a[i]] = 1;
}
fac[0] = 1;
up (i, 1, N) fac[i] = mul(i, fac[i - 1]);
up (i, 1, N - 1) pre[i] += pre[i - 1];
lex = mul(mul(N, pop(N, 1)), inv2);
up (i, 1, N) if (a[i] != -1) cpop(lex, a[i]);
}
void Solve(){
up (i, 1, N) {
if (a[i] != -1) {
int sum = mul(fac[cnt] , a[i] - calc(a[i]));
if (cnt >= 1) cpop(sum, mul(fac[cnt - 1], mul(cur, a[i] + 1 - pre[a[i]])));
cmul(sum, fac[N - i]);
upd(a[i], 1);
cpop(lex, pop(N - 1 - a[i], pop(pre[N - 1], pre[a[i]])));
}else {
int sum = mul(lex, fac[cnt - 1]);
if (cnt >= 2) cpop(sum, mul(fac[cnt - 2], mul(cur, cal2(cnt))));
cmul(sum, fac[N - i]);
cur++;
}
}
}
}

int main(){
using namespace solution;
Prepare();
Solve();
return 0;
}

{"mode":"full","isActive":false}

## Problem solution in C.

#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];
{
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;
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;
}

{"mode":"full","isActive":false}