You'll be given an array (of integers) and a threshold value as
input, write a program to return the number of critical events in
the array. An event between indices i<j is a critical
event if a_{i }> t∗a_{j},
where t is the threshold value given as input.

Could you please using Python and mergesort?

See Answer

Add Answer +20 Points

Community Answer

See all the answers with 1 Unlock

Get 4 Free Unlocks by registration

Get 4 Free Unlocks by registration

Hello Dear Student :>>> SOLUTION :>> The idea is to use the concept of merge sort and then count pairs according to the given conditions. Follow the steps below to solve the problem:Initialize a variable, say answer, to count the number of pairs satisfying the given condition.Repeatedly partition the array into two equal halves or almost equal halves until one element is left in each partition.Call a recursive function that counts the number of times the condition arr[i] > K**arr[j] and i < j is satisfied after merging the two partitions.Perform it by initializing two variables, say i and j, for the indices of the first and second half respectively.Increment j till arr[i] > K** arr[j] and j < size of the second half. Add (j-(mid+1)) to the answer and increment i.After completing the above steps, print the value of answer as the required number of pairs. # Python3 program for the above approach # Function to merge two sorted arrays def merge(arr, temp, l, m, r, K) : # i: index to left subarray i = l # j: index to right subarray j = m + 1 # Stores count of pairs that # satisfy the given condition cnt = 0 for l in range(m + 1) : found = False # Traverse to check for the # valid conditions while (j <= r) : # If condition satisfies if (arr[i] >= K * arr[j]) : found = True else : break j += 1 # While a[i] > K*a[j] satisfies # increase j # All elements in the right # side of the left subarray # also satisfies if (found) : cnt += j - (m + 1) j -= 1 # Sort the two given arrays and # store in the resultant array k = l i = l j = m + 1 ... See the full answer