FastPrepMinimum Distinct Prefix Cost

Minimum Distinct Prefix Cost

Chubb logoChubb● MediumNEW GRADOA
Learn

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 Chubb problems

See Chubb hiring insights
public long minimumDistinctPrefixCost(int[] arr) {
    // Write your code here.
}
arr[2,2,3,1,1]
expected9
Checking account…