FastPrep
Problem · Array

Subsequences of Three

Learn this problem
● MediumTiktokINTERNNEW GRADOA
See Tiktok hiring insights

Problem 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 = 1
    No explanation for now. Will provide it once find any :D

    Constraints

    • 3 ≤ n ≤ 103
    • 1 ≤ arr[i] ≤ 109
    • arr contains distinct elements.

    More Tiktok problems

    drafts saved locally
    public int calculateValidity(int[] arr) {
  // write your code here
}
    arr[2, 3, 1, 4]
    expected0
    checking account