HackerRank Prefix Cost
Consider an array arr of length n. The the cost of
the array is defined as the sum of the number of
distinct elements over all prefixes of the array. For
example, the cost of [1, 2, 11 is equal to distinct
elements in [11 + distinct elements in [1, 2] +
distinct elements in [1. 2. 11 = 1 + 2 + 2 = 5
Find the minimum cost among all possible
permutations of arr.
Note: A permutation is a rearrangement of
elements of an array into a new array. For example,
there are 24 permutations of array [1, 2, 3, 41. Some
of them are [2, 1, 4, 31, [4, 1, 2, 3] and [1, 4, 2, 31.
arr = [2,2,3,1,11
Consider the permutation [2, 2, 1, 1, 3]
• The numbers of distinct elements in prefix [21, [2,21,
[2,2,11, [2,2,1,11 and [2,2,1,1 3] are 1, 1, 2, 2 and 3
respectively.
• The cost of [2,2,1,1,3] = 1+1+2+2+3 = 9.
There are multiple permutations to arrive at