Problem Brief
Subsequences of Three
INTERNNEW GRADOA
See Tiktok online assessment and hiring insights
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 Description
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
1Example 1
Input
arr = [2, 3, 1, 4]
Output
0
Explanation
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| = 10.2Example 2
Input
arr = [1, 2, 4]
Output
1
Explanation
No explanation for now. Will provide it once find any :D
Constraints
Limits and guarantees your solution can rely on.
- 3 ≤ n ≤ 103
- 1 ≤ arr[i] ≤ 109
- arr contains distinct elements.