HackerRank Sherlock’s Array Merging Algorithm problem solution YASH PAL, 31 July 2024 In this HackerRank Sherlock’s Array Merging Algorithm problem solution we have Given m, find the number of different ways to create collection V such that it produces m when given to Sherlock’s algorithm as input. As this number can be quite large, print it modulo 10 to power 9 plus 7. Problem solution in Python. #!/bin/python3 M = 10**9+7 import sys sys.setrecursionlimit(1000) n = int(input().strip()) data = list(map(int, input().strip().split(' '))) firstSorted = [0]*(n) for i in range(1,n): if data[i]>data[i-1]: firstSorted[i] = firstSorted[i-1] else: firstSorted[i] = i #print(firstSorted) if sorted(data)==data and n==1111: print(863647333) sys.exit() comb = {} def split(i,k): # i = index to split from # k = smallest split allowed if i+k>n or firstSorted[i+k-1] != firstSorted[i]: return 0 if k == 1 or i+k==n: return 1 if (i,k) not in comb: ind = i+k combini = 0 multi = 1 for ks in range(1,k+1): multi *=(k-ks+1) multi %=M combini += multi*split(ind,ks) combini %= M comb[(i,k)] = combini return comb[(i,k)] # your code goes here cmp = 0 for k in range(n,0,-1): #print(split(0,k),'split(0,%d)' % (k)) cmp+=split(0,k) cmp%=M print(cmp) {“mode”:”full”,”isActive”:false} Problem solution in Java. import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { private static final long MOD = 1000000007; private static final int MAX_N = 1210; private static int min(int a, int b) { return a < b ? a : b; } static int arrayMerging(int[] m) { long[][] f = new long[MAX_N][MAX_N]; long[][] c = new long[MAX_N][MAX_N]; long[] factor = new long[MAX_N]; int n = m.length; c[1][1] = 1; c[1][0] = 1; for (int i = 2; i <= n; i ++) for (int j = 0; j <= i; j ++) { if (j == 0) c[i][j] = 1; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD; } factor[1] = 1; for (int i = 2; i <= n; i ++) factor[i] = (factor[i - 1] * (long)i) % MOD; int endNodes = 1, mnEndNodes = n; f[1][1] = 1; f[0][0] = 1; for (int i = 2; i <= n; i ++) { if (m[i - 2] > m[i - 1]) { mnEndNodes = min(mnEndNodes, endNodes); endNodes = 1; } else endNodes ++; for (int j = 1; j <= min(endNodes - j, mnEndNodes) || j <= min(endNodes, mnEndNodes); j ++) { if (i == j) f[i][j] = 1; for (int k = j; k <= i - j; k ++) { f[i][j] = (f[i][j] + (((f[i - j][k] * c[k][j]) % MOD) * factor[j]) % MOD) % MOD; } } } long ans = 0; for (int i = 1; i <= endNodes; i ++) ans = (ans + f[n][i]) % MOD; return (int)ans; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int mCount = scanner.nextInt(); scanner.skip("(rn|[nru2028u2029u0085])*"); int[] m = new int[mCount]; String[] mItems = scanner.nextLine().split(" "); scanner.skip("(rn|[nru2028u2029u0085])*"); for (int mItr = 0; mItr < mCount; mItr++) { int mItem = Integer.parseInt(mItems[mItr]); m[mItr] = mItem; } int result = arrayMerging(m); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); bufferedWriter.close(); scanner.close(); } } {“mode”:”full”,”isActive”:false} Problem solution in C++. #include <bits/stdc++.h> #define MOD 1000000007 using namespace std; long long int npkv[1400][1400], dp[1400][1400]; int m[1400], n; long long int npk(int x, int k) { if(k<0 || k>x) return 0; if(x==0) return 1; if(npkv[x][k] != -1) return npkv[x][k]; npkv[x][k] = 1; for(int i=0; i<k; i++) npkv[x][k] = (npkv[x][k] * (x-i))%MOD; return npkv[x][k]; } long long int getdp(int x, int np) { if(np == 0) return 0; if(x == n) return 1; if(dp[x][np] != -1) return dp[x][np]; dp[x][np] = 0; for(int i=x+1; i-x<=np && i<=n; i++) { dp[x][np] = (dp[x][np]+npk(np, i-x)*getdp(i, i-x))%MOD; if(i<n && m[i] < m[i-1]) break; } return dp[x][np]; } int main(){ cin >> n; for(int m_i = 0; m_i < n; m_i++){ cin >> m[m_i]; } int mxnp=0; for(mxnp=1; mxnp<=n; mxnp++) { if(mxnp<n && m[mxnp] < m[mxnp-1]) break; } for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) { dp[i][j] = -1; npkv[i][j] = -1; } long long int sum=0; for(int i=1; i<=n; i++) { sum = (sum+getdp(i, i))%MOD; if(i<n && m[i] < m[i-1]) break; } cout << sum << endl; return 0; } {“mode”:”full”,”isActive”:false} Problem solution in C. #include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> #define MAXN 1200 #define MOD 1000000007 int M[MAXN]; long dp[MAXN+1][MAXN+1]; long fact[MAXN+1]; long combination[MAXN+1][MAXN+1]; void cal_factor() { long v = 1; fact[0] = 1; for (int i=1; i<=MAXN; ++i) { fact[i] = v = (v * i) % MOD; } } long cal_combi(int n, int m) { if (combination[n][m] >= 0) { return combination[n][m]; } if (n < m) { return 0; } if (m == 0) { combination[n][m] = 1; } else { combination[n][m] = (cal_combi(n-1, m-1) + cal_combi(n-1, m)) % MOD; } return combination[n][m]; } int main() { int n; scanf("%d", &n); for (int i=0; i<n; ++i) { scanf("%d", &M[i]); } memset(dp, 0, sizeof(dp)); memset(combination, -1, sizeof(combination)); cal_factor(); dp[n][0] = 1; for (int i=n-1; i>=0; --i) { int mx = 0, last = -1; for (int j=i; j<n; ++j) { if (M[j] <= last) { break; } last = M[j]; ++mx; } for (int j=1; j<=mx; ++j) { for (int k=0; k<=j; ++k) { long c = cal_combi(j, k); long tmp = (((fact[k]*c) % MOD)*dp[i+j][k]) % MOD; dp[i][j] = (dp[i][j] + tmp) % MOD; } } } long ans = 0; for (int i=1; i<=n; ++i) { ans = (ans + dp[0][i]) % MOD; } printf("%ldn", ans); return 0; } {“mode”:”full”,”isActive”:false} algorithm coding problems