We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
def arrayMerging(data):
# Write your code here
n = len(data)
M = 10**9+7
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:
return 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
return cmp
Sherlock's Array Merging Algorithm
You are viewing a single comment's thread. Return to all comments →
python3
def arrayMerging(data): # Write your code here n = len(data) M = 10**9+7 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)