FastPrepMinimum Distinct Prefix Cost
Problem · Array

Minimum Distinct Prefix Cost

Learn this problem
● MediumGoldman Sachs logoGoldman SachsFULLTIMEINTERNOA

Problem 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[]) → long

Examples

Example 1

arr = [2,2,3,1,1]return = 9

One 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^5
  • 1 <= arr[i] <= 10^5

More Goldman Sachs problems

drafts saved locally
public long minimumDistinctPrefixCost(int[] arr) {
    // Write your code here.
}
arr[2,2,3,1,1]
expected9
checking account