HackerRank Swap Permutation problem solution

In this HackerRank Swap Permutation problem solution we have given an array A = [1, 2, 3, …, n]:

1. How many sequences (S1) can you get after exact k adjacent swaps on A?
2. How many sequences (S2) can you get after at most k swaps on A?

An adjacent swap can be made between two elements of the Array A, A[i] and A[i+1] or A[i] and A[i-1]. A swap otherwise can be between any two elements of the array A[i] and A[j] ∀ 1 ≤ i, j ≤ N, I ≠ j.

Problem solution in Python.

#!/bin/python3

import os
import sys


#
# Complete the swapPermutation function below.
#
def swapPermutation(n, k):
    #
    # Write your code here.
    #
    mod = 1000000007
    s = [1] + [0] * k
    t = [1] + [0] * k
    for i in range(1, n):
        temp = sum(s[max(k - i, 0):k]) % mod
        for j in range(k, 0, -1):
            s[j] = (s[j] + temp) % mod
            if j > i:
                temp = (temp + s[j - i - 1] - s[j - 1]) % mod
            else:
                temp = (temp - s[j - 1]) % mod
        for j in range(k, 0, -1):
            t[j] = (t[j] + i * t[j - 1]) % mod
    return sum(s[k % 2::2]) % mod, sum(t) % mod


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

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    result = swapPermutation(n, k)

    fptr.write(' '.join(map(str, result)))
    fptr.write('n')

    fptr.close()

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    public static List<Integer> swapPermutation(int n, int k) {
    // Write your code here
        long [][] dp0 = new long[n + 1][k + 1];
        long [][] sum0 = new long[n + 1][k + 2];
        int mod = 1000000007;
        for(int i = 0; i < n + 1; i++) dp0[i][0] = 1L;
        for(int i = 1; i < k + 2; i++) sum0[1][i] = sum0[1][i - 1] + dp0[1][i - 1];
        for(int i = 1; i < n + 1; i++) sum0[i][1] = 1L;


        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= k; j++){
                int head = Math.max(0, j - i + 1);
                dp0[i][j] = sum0[i - 1][j + 1] - sum0[i - 1][head];
                sum0[i][j + 1] = (sum0[i][j] + dp0[i][j]) % mod;
            }
        }

        long ans1 = 0L;
        for(int i = k; i >= 0; i -= 2) ans1 = (ans1 + dp0[n][i]) % mod;


        long [][] dp1 = new long[n + 1][k + 1];

        for(int i = 0; i <= n; i++) dp1[i][0] = 1L;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= k; j++){
                dp1[i][j] = (dp1[i - 1][j] + ((i - 1) * dp1[i - 1][j - 1]) % mod) % mod;
            }
        }
        long ans2 = 0L;

        for(int i = 0; i <= k; i++) ans2 = (ans2 + dp1[n][i]) % mod;
        List<Integer> ans = new ArrayList<>();
        ans.add((int)ans1);
        ans.add((int)ans2);

        return ans;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int k = Integer.parseInt(firstMultipleInput[1]);

        List<Integer> result = Result.swapPermutation(n, k);

        bufferedWriter.write(
            result.stream()
                .map(Object::toString)
                .collect(joining(" "))
            + "n"
        );

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


uint64_t mod = 1000000007;
uint64_t **dyn_adjswap;
uint64_t **dyn_anyswap;

int nsz = 2550;
int ksz = 2550;

void generate_adjswap()
{
    dyn_adjswap = new uint64_t*[nsz];
    
    for(int n=2; n<nsz; n++)
    {
    dyn_adjswap[n]=new uint64_t[ksz];
    if(n==2){
        for(int k=-1; k<ksz-1;k++) dyn_adjswap[n][k+1]=1;
        continue;
    }
    dyn_adjswap[n][0] = 0;
    for(int k=0; k<ksz-1; k++)
    {
        dyn_adjswap[n][k+1] = dyn_adjswap[n-1][k+1] + dyn_adjswap[n][k-1+1];
        if(k>=n) dyn_adjswap[n][k+1] += mod - dyn_adjswap[n-1][k-n+1];
        dyn_adjswap[n][k+1] %= mod;
    }
    }
}

void generate_anyswap()
{
    dyn_anyswap = new uint64_t*[nsz];
    
    for(int n=2; n<nsz; n++)
    {
    dyn_anyswap[n]=new uint64_t[ksz];
    if(n==2){
        for(int k=0; k<ksz;k++) dyn_anyswap[n][k]=1;
        continue;
    }
    dyn_anyswap[n][0] = 1;
    for(int k=1; k<ksz; k++)
    {
        dyn_anyswap[n][k] = dyn_anyswap[n-1][k] + (n-1)*dyn_anyswap[n-1][k-1];
        dyn_anyswap[n][k] %= mod;
    }
    }
}

uint64_t adjswap(int n, int k)
{
    return dyn_adjswap[n][k+1];
}

uint64_t anyswap_atmost(int n, int k)
{
    return (dyn_anyswap[n][k]+dyn_anyswap[n][k-1]) % mod;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    generate_adjswap();
    generate_anyswap();

    int n, k;
    cin >> n >> k;
    cout << adjswap(n,k) << " " << anyswap_atmost(n,k) << endl;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(X,Y) (X>Y)?Y:X
#define f(i,a,b) for(int i = (a); i <= (b); i++)

typedef long long ll;

const ll MOD = 1000000007;
int N, K;
ll A[2505][2505], T[2505], B[2505][2505];

void update1(int x, ll v)
{
    while(x <= 2501)
    {
        T[x] = (T[x]+v) % MOD;
        x += x&-x;
    }
}

void update2(int l, int r, ll v)
{
    l++, r++;
    update1(l,v), update1(r+1,-v);
}

ll query(int x)
{
    x++;
    ll ret = 0;
    while(x>0)
    {
        ret = (ret+T[x]) % MOD;
        x -= x&-x;
    }
    return ret;
}

int main()
{
    
    A[1][0] = 1;
    f(i,1,2499)
    {
        f(j,0,2500) update2(j,min(j+i,2500),A[i][j]);
        f(j,0,2500) A[i+1][j] = query(j);
        f(j,0,2501) T[j] = 0;
    }
    
    
    B[1][1] = 1;
    f(i,1,2499) f(j,1,i)
    {
        B[i+1][j+1] = (B[i+1][j+1] + B[i][j]) % MOD;
        B[i+1][j] = (B[i+1][j] + B[i][j]*i) % MOD;
    }
    
    
    int N;
    int K;
    scanf("%d",&N);
    scanf("%d",&K);
    ll ans = 0, ans2 = 0;
    for(int j = K; j >= 0; j -= 2) ans += A[N][j];
    f(i,0,min(K,N-1)) ans2 += B[N][N-i];
    ll a1 = ans%MOD;
    ll a2 = ans2%MOD;
    printf("%lld %lldn",a1,a2);
}