HackerRank Sherlock’s Array Merging Algorithm problem solution

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)

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