Minimum Distinct Prefix Cost
Goldman Sachs● MediumFULLTIMEINTERNOAProblem statement
You are given an integer array arr of length n.
The cost of an array is the sum, over all of its prefixes, of the number of distinct values in each prefix. In other words, for every index i, count the distinct values in arr[0..i] and add all of those counts.
You may rearrange arr in any order. Return the minimum possible cost among all permutations of arr.
Function
minimumDistinctPrefixCost(arr: int[]) → longExamples
Example 1
arr = [2,2,3,1,1]return = 9One optimal permutation is [2,2,1,1,3]. Its prefix distinct counts are 1, 1, 2, 2, 3, so the total cost is 1 + 1 + 2 + 2 + 3 = 9.
Constraints
1 <= n <= 10^51 <= arr[i] <= 10^5