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()

Problem solution in Java.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        USED_Y.add(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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader br = new BufferedReader(new FileReader("D:\cards44.txt"));
        //BufferedReader br = new BufferedReader(new FileReader("D:\cards41.txt"));
        int n = Integer.parseInt(br.readLine());
        int[] perm = new int[n];
        StringTokenizer permTkn = new StringTokenizer(br.readLine());

        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};
        }
    }
}

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 cadd(a,b)        a = add (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]);
                cadd(ans, sum);
                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]);
                cadd(ans, sum);
                cur++;
            }
        }
        printf("%dn", add(ans, fac[cnt]));
    }
}

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

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];
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("%lldn", ans);
return 0;
}