In this HackerRank Swap Permutation problem solution we have given an array A = [1, 2, 3, …, n]:
- How many sequences (S1) can you get after exact k adjacent swaps on A?
- 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); }