HackerRank Sherlock’s Array Merging Algorithm problem solution YASH PAL, 31 July 202425 January 2026 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 109 + 7.Notes:Two collections of arrays are different if one of the following is true:Their sizes are different.Their sizes are the same but at least one array is present in one collection but not in the other.Two arrays, A and B, are different if one of the following is true:Their sizes are different.Their sizes are the same, but there exists an index i such that ai != bi.HackerRank Sherlock’s Array Merging Algorithm 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) Sherlock’s Array Merging Algorithm 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(); } } 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; } 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; } Algorithms coding problems solutions AlgorithmsHackerRank