Maximum Supplier Profit

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given an array arr of N positive integers, where arr[i] represents the number of products available from the i-th supplier. You are also given a positive integer M, which is the total number of products you must sell.

The profit gained from selling a single product from a supplier is equal to the number of products that supplier currently has. Each time you sell a product from a supplier, their count of available products decreases by one.

Your task is to find the maximum possible profit you can achieve by selling exactly M products.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two space-separated integers, N (the number of suppliers) and M (the number of products to sell).

The second line contains N space-separated integers, representing the elements of the arr array.

Output Format:

Print a single integer representing the maximum possible profit.

Note:

To maximize profit at any given step, it is always optimal to sell from the supplier who currently has the most products. A simple simulation of selling one product at a time might be too slow if M is large. A more efficient approach involves sorting the suppliers and selling products in "layers" from the top suppliers. The total profit can be very large, so be sure to use a 64-bit integer type (like long in Java or long long in C++) for your calculations.

Sample Input 1:

2 4
4 6

Sample Output 1:

Explanation for Sample 1:

The greedy strategy is to always sell from the supplier with the most items.
  Sell from supplier 2 (6 items): Profit = 6. Items left: {4, 5}.
  Sell from supplier 2 (5 items): Profit = 6 + 5. Items left: {4, 4}.
  Sell from supplier 1 or 2 (4 items): Profit = 6 + 5 + 4. Items left: {3, 4}.
  Sell from supplier 2 (4 items): Profit = 6 + 5 + 4 + 4 = 19. Items left: {3, 3}.

Sample Input 2:

3 2
1 2 3

Sample Output 2:

Explanation for Sample 2:

Sell from supplier 3 (3 items): Profit = 3. Items left: {1, 2, 2}.
Sell from supplier 2 or 3 (2 items): Profit = 3 + 2 = 5. Items left: {1, 1, 2}.

Expected Time Complexity:

The expected time complexity is O(N log N).

Constraints:

1 <= N <= 10^5
1 <= M <= 10^9
1 <= arr[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Maximum Supplier Profit

Console