Subsequences of Three
TikTok● MediumINTERNNEW GRADOAProblem statement
Given an array of n integers, arr[n], determine all of its subsequences S of three elements and find the validity of arr.
validity = min{3 * abs(mean(S) - median(S)) for all S}
A subsequence is a sequence that can be derived from a sequence by deleting zero or more elements without changing the order of the remaining elements, for example [3, 4] is a subsequence of [5, 3, 2, 4].
Note
mean(A)is the average of the array (the sum of the array divided by the size of the array).median(A)is the middle value of an ordered set of numbers with an odd number of elements.abs(x)is the absolute value of an integer.
Function
calculateValidity(arr: int[]) → int
Complete the function calculateValidity in the editor.
calculateValidity has the following parameters:
int arr[n]: the series of integers
Returns
int: the validity of the series of integers
Examples
Example 1
arr = [2, 3, 1, 4]return = 0
The subsequences of three elements from the array [2, 3, 1, 4] are [2, 3, 1], [2, 3, 4], [2, 1, 4], and [3, 1, 4]. The validity for each subsequence is calculated as follows:
[2, 3, 1]: mean = (2 + 3 + 1) / 3 = 2, median = 2, validity = 3 * |2 - 2| = 0[2, 3, 4]: mean = (2 + 3 + 4) / 3 = 3, median = 3, validity = 3 * |3 - 3| = 0[2, 1, 4]: mean = (2 + 1 + 4) / 3 = 2.33, median = 2, validity = 3 * |2.33 - 2| = 1[3, 1, 4]: mean = (3 + 1 + 4) / 3 = 2.67, median = 3, validity = 3 * |2.67 - 3| = 1
The minimum validity among all subsequences is 0.
Example 2
arr = [1, 2, 4]return = 1No explanation for now. Will provide it once find any :D
Constraints
- 3 ≤ n ≤ 103
- 1 ≤ arr[i] ≤ 109
- arr contains distinct elements.