Sell Diminishing Bricks

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
6 upvotes
Asked in companies
AmazonHikeSoft Suave

Problem statement

Ninja has started a new business of selling bricks. There are ‘N’ types of bricks of distinct types present in his shop, and each brick’s cost is the number of bricks of that type currently present in his shop. The total number of each type of brick in the shop is given in an array 'ARR'. Ninja has received an order of ‘L’ bricks in his shop. Your task is to find the maximum profit Ninja can attain by this order.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, 'N' and 'L', denoting the number of elements in the array 'ARR', and the number of bricks ordered by the customer respectively.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.
Output Format : 
For each test case, print a single integer - the maximum profit Ninja can attain by the order.    

Print the output of each test case in a separate line.
Constraints : 
1 <=  T  <= 100
1 <=  N <= 10^3
1 <= ARR[i] <= 10^3
1 <=  L  <= min(SUM(ARR, 10^6))


Time limit: 1 sec
Sample Input 1 :
2
3 2 
1 3 5 
3 3
1 3 5
Sample Output 1 :
9
12
Explanation Of Sample Input 1 :
For the first test case, 
If Ninja sells the brick having cost 5 two times. After the transaction of the first brick, there are only 4 bricks left of that type due to which the cost of the following brick is 4 then the total profit will be 5 + 4 = 9, which is the maximum profit possible. Hence, the answer is 9 in this case.  

For the second test case,
If Ninja sells the brick having cost 5 two times. After the transaction of the two bricks, There are only 3 bricks left of that type. Now, there are 2 distinct bricks having cost 3. If Ninja sells any brick from them to the customer, then the total profit will be 5+4+3=12, which is the maximum profit possible. Hence, the answer is 12 in this case.
Sample Input 2 :
2
3 4
1 7 8 
4 4 
5 5 5 5
Sample Output 2 :
28
20
Hint

Try to sell the brick with the maximum cost for each of L transactions to the customer.

Approaches (4)
Brute Force

The idea is to sell the bricks having maximum cost first to the customer to obtain the maximum total profit. Therefore, our approach will be to find the brick with the maximum cost for each of the L transactions and update the cost of that brick after every transaction of the brick to the customer. Note that, if there are many distinct bricks having the same cost then Ninja could choose any brick from them to sell to a customer.

 

Algorithm:

  • We will set the variable maxProfit as 0. The variable maxProfit stores the maximum total profit.
  • Iterate brickNumber from 1  to L.
    • Iterate through the array ARR, and find the brick having the maximum cost and increment maxProfit by the cost of the brick
    • Decrement the cost of the brick having the maximum cost in the array ARR by 1 as the number of bricks remaining in the shop is decreased by 1 after the transaction of the brick to the customer
  • Return the variable maxProfit.
Time Complexity

O(N*L), where 'N' denotes the number of elements in the array and 'L' denotes the number of bricks ordered by the customer.

 

We are traversing through the array ARR to find the brick with the maximum cost for each transaction of L bricks to the customer. Hence, the overall Time Complexity is O(N*L).

Space Complexity

O(1).

 

Constant extra space is being used. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Sell Diminishing Bricks
Full screen
Console