HackerRank Swap Permutation Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Swap Permutation Problem Solution.

You are 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.

Input Format

First and only line contains n and k separated by space.

Constraints

1 ≤ n ≤ 2500
1 ≤ k ≤ 2500

Output Format

Output S1 % MOD and S2 % MOD in one line, where MOD = 1000000007.

Sample Input

3 2

Sample Output

3 6

Explanation

Original array: [1, 2, 3]
1. After 2 adjacent swaps:
We can get [1, 2, 3], [2, 3, 1], [3, 1, 2] ==> S1 == 3

2. After at most 2 swaps:
1) After 0 swap: [1, 2, 3]
2) After 1 swap: [2, 1, 3], [3, 2, 1], [1, 3, 2].
3) After 2 swaps: [1, 2, 3], [2, 3, 1], [3, 1, 2]
==> S2 == 6
HackerRank Swap Permutation Problem Solution
HackerRank Swap Permutation Problem Solution

Swap Permutation C Solution

#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 %lld\n",a1,a2);
}

Swap Permutation C++ Solution

#include <bits/stdc++.h>
using namespace std;
#define M int (1e9+7)
long long sumof(long long &a, long long &b) {
    return (a + b) % M;
}
int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<long long>>dp(n, vector<long long>(k + 1, 0));
    for (int i = 0; i < n; i++)
        dp[i][0] = 1;
    long long ans1;
    if (n == 1 || n == 2)
        ans1 = 1;
    else {
        for (int i = 0; i <= k; i++)
            dp[1][i] = 1;
        for (int i = 2; i < n; i++) {
            for (int j = 1; j <= min(k, i); j++)
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % M;
            for (int j = i + 1; j <= k; j++)
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] + M - dp[i - 1][j - i - 1]) % M;
        }
        ans1 = dp[n - 1][k];
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= k; j++)
            dp[i][j] = 0;
    long long ans2 = 0;
    if (n == 1)
        ans2 = 1;
    else{
        dp[1][0] = 1, dp [1][1] = 2;
        for (int i = 2; i <= k; i++)
            dp[1][i] = 2;
        for (int i = 2; i < n; i++){
            dp[i][0] = 1;
            for (int j = 1; j <= k; j++)
                dp[i][j] = ((i * dp[i - 1][j - 1]) % M + dp[i - 1][j]) % M;
        }
        ans2 = dp[n - 1][k];
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}

Swap Permutation C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'swapPermutation' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER k
     */

    public static List<int> swapPermutation(int n, int k)
        {
            long[][] dp = new long[n + 1][];

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

            for (int i = 0; i <= n; i++)
            {
                dp[i] = new long[k + 1];
                dp1[i] = new long[k + 1];


            }
            int mod = 1000000007;
            for (int i = 0; i < n + 1; i++) dp[i][0] = 1;

            int a = 1, b = 2, c = 2;

            for (int i = 2; i <= n; i++)
            {
                c = b;
                a = Math.Min(a, k);
                for (int j = 1; j <= a; j++)
                {
                     dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
                    
                    if (j >= b)
                    {
                        if (dp[i][j] < dp[i - 1][b - c]) dp[i][j] += mod - dp[i - 1][b - c];
                        else dp[i][j] -= dp[i - 1][b - c];
                        c--;

                    }
                }
                a += i;
                b++;

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



            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 = 0;

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

            return ans;
        }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

        int n = Convert.ToInt32(firstMultipleInput[0]);

        int k = Convert.ToInt32(firstMultipleInput[1]);

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

        textWriter.WriteLine(String.Join(" ", result));

        textWriter.Flush();
        textWriter.Close();
    }
}

Swap Permutation Java Solution

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

Swap Permutation JavaScript Solution

Array.matrix = function (numrows, numcols, initial) {
    var arr = [];
    for (var i = 0; i < numrows; ++i) {
        var columns = [];
        for (var j = 0; j < numcols; ++j) {
            columns[j] = initial;
        }
        arr[i] = columns;
    }
    return arr;
};

function processData(input) {
    //Enter your code here
    var inputArray = input.split(" ");
    var n = Number(inputArray[0]);
    var k = Number(inputArray[1]);
    var mod = 1000000007;
    var first = countingPermutationWithKAdajacentSwap(n, k, mod);
    var second = countingPermutationWithKSwapAtMost(n, k, mod);
    console.log(first + " " + second);


}

function countingPermutationWithKAdajacentSwap(n, k, mod) {
    var dp = Array.matrix(2, k + 1, 0);
    dp[0][0] = 1;
    for (var i = 1; i <= n; i++) {
        var sum = 0;
        for (var j = 0; j <= k; j++) {
            sum += dp[0][j];
            sum = sum % mod;
            if (j >= i) {
                sum += mod;
                sum -= dp[0][j - i];
                sum = sum % mod;
            }
            dp[1][j] = sum;
        }
        var temp = dp[1];
        dp[1] = dp[0];
        dp[0] = temp;
    }
    var res = 0;
    for (var j = k; j >= 0; j -= 2) {
        res += dp[0][j];
        res = res % mod;
    }
    return res;
}

function countingPermutationWithKSwapAtMost(n, k, mod) {
    var dp = Array.matrix(2, k + 1, 0);
    var res = 0;
    dp[0][0] = 1;
    for (var i = 1; i <= n; i++) {
        dp[1][0] = 1;
        for (var j = 1; j <= k; j++) {
            dp[1][j] = (dp[0][j] + (((i - 1) * dp[0][j - 1]) % mod)) % mod;
        }
        var temp = dp[1];
        dp[1] = dp[0];
        dp[0] = temp;

    }
    for (var i = 0; i <= k; i++) {
        res += dp[0][i];
        res = res % mod;
    }
    return res;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
    processData(_input);
});

Swap Permutation Python Solution

#!/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()
c C# C++ HackerRank Solutions java javascript python