Skip to content
TheCScience
TheCScience
  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
TheCScience
HackerRank Swap Permutation Problem Solution

HackerRank Swap Permutation Problem Solution

Yashwant Parihar, August 7, 2023August 1, 2024

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 CcppCSharpHackerrank Solutionsjavajavascriptpython

Post navigation

Previous post
Next post
  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 TheCScience | WordPress Theme by SuperbThemes