Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • 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
THECSICENCE

Learn everything about computer science

HackerRank Sherlock’s Array Merging Algorithm

Yashwant Parihar, June 23, 2023August 1, 2024

In this post, we will solve HackerRank Sherlock’s Array Merging Algorithm Problem Solution.

Watson gave Sherlock a collection of arrays V. Here each V; is an array of variable length. It
is guaranteed that if you merge the arrays into one single array, you’ll get an array, M, of n
distinct integers in the range [1, n].
Watson asks Sherlock to merge V into a sorted array. Sherlock is new to coding, but he accepts the challenge and writes the following algorithm:
M] (an empty array).
knumber of arrays in the collection V.

  • While there is at least one non-empty array in V
  • T + [] (an empty array) and i + 1.
  • While i <k:
    If V; is not empty:
    Remove the first element of V; and push it to T.
    i+i+1.
  • While T is not empty:
    Remove the minimum element of T and push it to M.
  • Return M as the output.
    Let’s see an example. Let V be {[3, 5], [1], [2,4]}.

Sherlock isn’t sure if his algorithm is correct or not. He ran Watson’s input, V. through his pseudocode algorithm to produce an output. M. that contains an array of n integers. However, Watson forgot the contents of V and only has Sherlock’s M with him! Can you help Watson reverse-engineer M to get the original contents of V?
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 a, #bi.
Input Format
The first line contains an integer, n. denoting the size of array M.
The second line contains n space-separated integers describing the respective values of
mo, m1,…, mn-1.

Sample Input 0

3
1 2 3

Sample Output 0

4
HackerRank Sherlock's Array Merging Algorithm Problem Solution
HackerRank Sherlock’s Array Merging Algorithm Problem Solution

Sherlock’s Array Merging Algorithm C++ Solution

#include <bits/stdc++.h>
using namespace std;
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ff(i,a,b) for(int i = (a); i <= (b); i++)
#define fr(i,a,b) for(int i = (a); i >= (b); i--)
#define REP( i , n ) for( int i = 0 ; i < n ; i++ )
#define REPI( n , i ) for( int i = n ; i >= 0 ; i-- )
#define sc( x ) scanf( "%d" , &x )
#define sc2( x , y ) scanf( "%d%d" , &x , &y )
#define scd( x ) scanf( "%.9f" , &x )
#define scl( x ) scanf( "%I64d" , &x )
#define pf( x ) printf( "%d\n" , x )
#define pfd( x ) printf( "%.9f\n" , x )
#define pfl( x ) printf( "%I64d\n" , x )
#define rrc( x ) return cout << x , 0 ;
#define all( v ) v.begin(),v.end()
#define all_r( v ) v.rbegin() , v.rend()
#define fi first
#define se second
#define endl '\n'
#define SZ(a) int(a.size())
#define pb push_back
#define cln( x , v ) memset( x , v , sizeof( x ) )
#define pi acos(-1.0)
#define e2( x ) ( 1LL*( x )*( x ) )
#define r2( x ) sqrt( 1.0*( x ) )
#define ones(x) __builtin_popcount(x)
#define MCM( a , b ) ( ( a*b )/( __gcd( a , b ) ) )
#define ddd cout << "despues" << endl ;
#define sss cout << "------------------" << endl ;
#define aaa cout << "antes" << endl ;
#define da( a , b ) ( (a)/(b) - ( (a) < 0 && (a)%(b) != 0 ) )
#define ceil_( a , b ) ( da( (a) , (b) ) + ((a)%(b) > 0) )
#define Mm greater<int>
#define nxtPerm next_permutation
#define L( n ) 2 * n
#define R( n ) 2 * n + 1
#define A 1 , 0 , n - 1
#define endl '\n'

typedef double db ;
typedef long double ld ;
typedef long long ll ;
typedef vector<int> vi ;
typedef vector<vi> vvi ;
typedef vector<ll> vl ;
typedef vector<bool> vb ;
typedef pair<int,int> pii ;
typedef vector<pii> vpii ;
const ld EPS = 1e-8 ;
const int INF = (int)( INT_MAX - 100 ) ;
const ll mod = (int)( 1e+9 + 7 ) ;
const int N = (int)( 1200 ) ;
int days_month[ 12 ] = { 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 };
//inline ll modulo( ll num ){ ( ( num %= mod ) += mod ) %= mod ; return num ; }
//inline ll pot( int b , int e ){ ll p = 1 ; REP( i , e ) p = (p*b)%mod ; return p ; }

ll C[ N + 2 ][ N + 2 ] ;
ll F[ N + 2 ] ;
int lim[ N + 2 ] ;
int num[ N + 2 ] ;
int nxtL[ N + 2 ] ;
int n ;

void init() {
	for( int i = 0 ; i <= N ; i ++ ) {
		for( int j = 0 ; j <= i ; j ++ ){
			if( i == j || j == 0 ) C[ i ][ j ] = 1 ;
			else C[ i ][ j ] = ( C[ i - 1 ][ j - 1 ] + C[ i - 1 ][ j ] ) % mod ;
		}
	}
	F[ 0 ] = 1 ;
	for( int i = 1 ; i <= N ; i ++ ) {
		F[ i ] = ( F[ i - 1 ]*i )%mod ;
	}
	for( int i = n ; i >= 1 ; i -- ) {
		nxtL[ i ] = 1 ;
		if( lim[ i ] == lim[ i + 1 ] ) {
			nxtL[ i ] += nxtL[ i + 1 ] ;
		}
	}
}

bool used[ N + 2 ][ N + 2 ] ;
int memo[ N + 2 ][ N + 2 ] ;

int dp( int p , int last ) {
	if( p > n ) return 1 ;
	if( used[ p ][ last ] ) return memo[ p ][ last ] ;
	used[ p ][ last ] = true ;
	int &ans = memo[ p ][ last ] = 0 ;
	int max_len = min( last , nxtL[ p ] ) ;
	for( int len = max_len ; len >= 1 ; len -- ) {
		ll perm = ( F[ len ]*C[ last ][ len ] ) % mod ;
		if( p == 1 ) perm = 1 ;
		ans += ( perm*dp( p + len , len ) ) % mod ;
		if( ans >= mod ) ans -= mod ;
	}
	return ans ;
}

int main()
{
//	ios_base::sync_with_stdio(0);
	scanf( "%d" , &n ) ;
	for( int i = 1 ; i <= n ; i ++ ) {
		scanf( "%d" , &num[ i ] ) ;
	}
	for( int i = 1 ; i <= n ; i ++ ) {
		lim[ i ] = lim[ i - 1 ] ;
		if( num[ i - 1 ] > num[ i ] ) {
			lim[ i ] ++ ;
		}
	}
	init() ;
	printf( "%d" , dp( 1 , n ) ) ;

	return 0 ;
}


Sherlock’s Array Merging Algorithm C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
/// <summary>
/// Sherlock's Array Merging Algorithm
/// https://www.hackerrank.com/contests/university-codesprint-2/challenges/sherlocks-array-merging-algorithm
/// </summary>
class Solution5
{
    // ---------------------------------------------------------------------
    static int[][] FiF(int nmax, int modulus)
    {
        int[][] fif = new int[2][];
        fif[0] = new int[nmax + 1];
        fif[0][0] = 1;
        for (int i = 1; i <= nmax; i++) fif[0][i] = (int)(((long)fif[0][i - 1] * i) % modulus);
        long a = fif[0][nmax];
        long b = modulus;
        long p = 1;
        long q = 0;
        while (b > 0)
        {
            long c = a / b;
            long d = a;
            a = b;
            b = d % b;
            d = p;
            p = q;
            q = d - c * q;
        }
        fif[1] = new int[nmax + 1];
        fif[1][nmax] = (int)(p < 0 ? p + modulus : p);
        for (int i = nmax - 1; i >= 0; i--) fif[1][i] = (int)(((long)fif[1][i + 1] * (i + 1)) % modulus);
        return fif;
    }
    static long Choose(int n, int r, int[][] fif, int modulus)
    {
        if (n < 0 || r < 0 || r > n) return 0;
        long factn = fif[0][n];
        long invFactr = fif[1][r];
        long invFactnr = fif[1][n - r];

        long c1 = ((long)fif[0][n] * fif[1][r]) % modulus;
        long c2 = (c1 * fif[1][n - r]) % modulus;

        return ((((long)fif[0][n] * fif[1][r]) % modulus) * fif[1][n - r]) % modulus;
    }
    // ---------------------------------------------------------------------

    const int R = 1000000007;
    static int N = 0;
    static int[] A = null;
    static int[] B = null;
    static int[][] FIF = null;
    static int[][] DP = null;
    static int[][] C = null;

    static int wdp0()
    {
        long ways = 0;
        int wxm = Math.Min(B[0], N);
        for (int iwx = 1; iwx <= wxm; iwx++)
            ways = (ways + wdp(iwx, iwx)) % R;
        return (int)ways;
    }

    static int wdp(int ix, int wx)
    {
        if (ix == N || wx == 1) return 1;
        if (DP[ix][wx] > -1) return DP[ix][wx];

        long ways = 0;
        int wxm = Math.Min(Math.Min(wx, B[ix]), N - ix);

        for (int iwx = 1; iwx <= wxm; iwx++)
        {
            long c = C[wx][iwx];
            if (c < 0)
            {
                c = (Choose(wx, iwx, FIF, R) * FIF[0][iwx]) % R;
                C[wx][iwx] = (int)c;
            }

            //long c = (Choose(wx, iwx, FIF, R) * FIF[0][iwx]) % R;
            ways = (ways + (c * wdp(ix + iwx, iwx)) % R) % R;
        }

        DP[ix][wx] = (int)ways;
        return DP[ix][wx];
    }

    static void Main(String[] args)
    {
        TextReader tIn = Console.In;
        TextWriter tOut = Console.Out;

        N = int.Parse(tIn.ReadLine());
        A = tIn.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(p => int.Parse(p)).ToArray();

        B = new int[N];
        int b = 1;
        for (int i = N - 1; i >= 0; i--)
        {
            B[i] = b++;
            if (i > 0 && A[i - 1] > A[i]) b = 1;
        }

        FIF = FiF(1200 + 1, R);

        DP = new int[N][];
        for (int i = 0; i < N; i++)
        {
            DP[i] = new int[N + 1];
            for (int j = 0; j <= N; j++) DP[i][j] = -1;
        }

        C = new int[N + 1][];
        for (int i = 0; i <= N; i++)
        {
            C[i] = new int[N + 1];
            for (int j = 0; j <= N; j++) C[i][j] = -1;
        }

        tOut.WriteLine(wdp0());
    }

}

Sherlock’s Array Merging Algorithm Java Solution

import java.io.*;
import java.util.*;
import java.math.*;
public class Solution {
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    
    public static long inverseMOD( int a ){
        if( a == 0 ) return 1L;
        
        long t = 0L;
        long r = MOD;
        long newt = 1L;
        long newr = (long)a;
        long quotient;
        while( newr != 0L ){
            quotient = r / newr;

            t -= quotient * newt;
            r -= quotient * newr;

            if( r != 0L ){
                quotient = newr / r;
                newt -= quotient * t;
                newr -= quotient * r;
            }else{
                r = newr;
                t = newt;
                break;
            }
        }
        if( r > 1L ){
            return -1L;
        }
        if( t < 0L ) t += MOD;
        return t;
    }
    
    static HashMap<Integer,Long> C;
    static long I[];
    static int F[];
    static long FI[][];
    static long MOD = 1000000007L;
    static long MODLIMIT = Long.MAX_VALUE / MOD;
    static long MODSUMLIMIT = Long.MAX_VALUE - MOD*10L;
    static int S[];
    static int M[];
    static int mi;
    static int N;
    public static long solve( int blockindex, int funnellimit, int blocksize ){
//StringBuilder sb = new StringBuilder();
//sb.append( "Solve M["+blockindex+"]="+blocksize+"/"+(blockindex == mi ? 0 : M[blockindex] )+" with funnel limit "+funnellimit+" = ");
        
        if( funnellimit == 1 ){
//System.out.println( sb.toString()+"1");
            return 1L;
        }
        
        if( funnellimit > blocksize ){
//System.out.println( sb.toString()+"-1");
            return -1L;
        }
        
        if( blocksize == funnellimit ){
            if( blockindex == mi-1 ){
//System.out.println( sb.toString()+"1");
                return 1L;
            }
            
            int key = funnellimit*N + (S[blockindex] + M[blockindex] - blocksize);
            if( C.get(key) != null ){
                return C.get(key);
            }
            
            long p = 0;
            long t;
            blocksize = M[++blockindex];
            for( int f = (blocksize > funnellimit ? funnellimit : blocksize ); f != 0; f-- ){
                t = solve( blockindex, f, blocksize );
                if( t < 0L ) continue;

                //t *= FI[funnellimit][funnellimit-f];
                //if( t > MODLIMIT ) t%=MOD;
                t *= (long)F[funnellimit];
                if( t >= MODLIMIT ) t%=MOD;

                t *= I[funnellimit-f];
                if( t >= MODLIMIT ) t%=MOD;

                p += t;
                //if( p > MODSUMLIMIT ) p%=MOD;
            }
            
            if( p > MOD ) p%=MOD;
//System.out.println( sb.toString()+p);
            C.put( key, p );
            return p;
        }
        
        
        int key = funnellimit*N + (S[blockindex] + M[blockindex] - blocksize);
        if( C.get(key) != null ){
            return C.get(key);
        }
        
        
        long p = 0L;
        long t;
        blocksize -= funnellimit;
        for( int f = (blocksize > funnellimit ? funnellimit : blocksize ); f != 0; f-- ){
            t = solve( blockindex, f, blocksize );
            if ( t < 0L ) continue;
            
            t *= (long)F[funnellimit];
            if( t >= MODLIMIT ) t%=MOD;

            t *= I[funnellimit-f];
            if( t >= MODLIMIT ) t%=MOD;
            
            p += t;
            //if( p > MODSUMLIMIT ) p%=MOD;
        }
        
        if( p >= MOD ) p%=MOD;
//System.out.println( sb.toString()+p);
        C.put( key, p );
        return p;
    }
    public static void main(String[] args) throws IOException {
//        long start = System.nanoTime();    
        Reader in=new Reader();
        
        N = in.nextInt();
        int Np1 = N+1;
        
        {
            C = new HashMap<Integer,Long>(N);
        }
        
        M = new int[N];
        S = new int[N+1];
        mi = 0;
        {
            S[0] = 0;
            
            int prev = in.nextInt();
            int streak = 1;
            int cur;
            for( int i = 1; i < N; i++ ){
                cur = in.nextInt();
                if( cur < prev ){
                    S[mi+1] = S[mi]+streak;
                    M[mi++] = streak;
                    streak = 1;
                    prev = cur;
                }else{
                    ++streak;
                    prev = cur;
                }
            }
            S[mi+1] = S[mi]+streak;
            M[mi++] = streak;
            
            F = new int[M[0]+1];
            I = new long[M[0]+1];
            long fac = 1L;
            F[0] = 1;
            I[0] = 1L;
            for( int i = 1; i <= M[0]; i++ ){
                fac *= (long)i;
                if(fac >= MOD){
                    fac%=MOD;
                }
                F[i] = (int)fac;
                I[i] = inverseMOD( (int)fac );
            }
            
            FI = new long[M[0]+1][M[0]+1];
            for( int f = M[0]; f != 0; f-- ){
                for( int i = f; i != -1; i-- ){
                    FI[f][i] = ((long)F[f]*I[i])%MOD;
                }
            }
        }
        
        
        long p = 1;
        for( int f = 2; f < Np1; f++ ){
            long t = solve(0,f,M[0]);
            if( t < 0L ) continue;
            p += t;
            if( p > MODSUMLIMIT ) p%=MOD;
        }
        System.out.print( p%MOD );
        in.close();
    }
}

Sherlock’s Array Merging Algorithm Python Solution

#!/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)
C# C++ HackerRank Solutions java python cppCSharpHackerrank Solutionsjavapython

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 THECSICENCE | WordPress Theme by SuperbThemes