Last Updated: 10 Apr, 2021
Sell Diminishing Bricks
Moderate
Asked in companies
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.
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
Approaches
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.
In this approach, we will maintain a heap and insert the cost of all bricks into the heap. We will use the heap to find the brick with maximum cost and sell it to the customer for each of the L transactions. After selling that brick, we will update the cost of the brick sold to the customer after the transaction and insert the updated cost into the heap.
Algorithm:
- We will maintain a Max-heap and insert the cost of all distinct bricks present in the array ARR into the heap.
- We will set the variable maxProfit as 0. It will store the maximum total profit.
- Iterate brickNumber from 1 to L.
- Find the brick having the maximum cost through the heap and increment maxProfit by the cost of the brick
- Decrement the cost of that brick by 1 as the number of bricks remaining in the shop is decreased by 1 after the transaction of the brick to the customer and insert the new cost of the brick into the heap
- Return the variable maxProfit.
The basic idea is to always try to sell the brick having maximum cost until that brick offers maximum profit.
Therefore, our approach will be to sort the input array in descending order and maintain a pointer placed at the second element of the array ARR. The first element in the array will offer maximum profit until its cost is greater than the array’s second element. At each step, we will find the total number of transactions of bricks to the customer to reduce the value of bricks to the value being pointed by the pointer and compare the total number of transactions with L. If L is greater, then increment the total profit by profit to reduce brick’s value to the value pointed by the pointer and decrement L by the number of transactions to reduce brick’s value and move the pointer ahead, otherwise, we will find the minimum value to which value of bricks could be reduced with the remaining L and update the total profit.
Let’s take ARR=[6,5,4,2], and the pointer will be pointing at value 5, so we will try to find the number of transactions to reduce the value of brick 6 to 5, that is 1, and move the pointer ahead. After 1 transaction of brick to the customer, ARR will be [5,5,4,2], and the pointer will be pointing at value 4. We will try to find the number of transactions to reduce both bricks of value 5 to 4, that is 2. After 3 transactions of brick to the customer, ARR will be [4,4,4,2]. At each step, we will compare the number of transactions to reduce brick’s value with L.
The formula used while updating the total profit is the sum of the n natural number (n*(n+1))/2 as the cost of the sold brick to the customer is decreased by 1 after each transaction. This approach works since we are trying to sell maximum-cost bricks to the customer to obtain maximum total profit.
Algorithm:
- Sort the array ARR and insert 0 in ARR. In the approach, we are trying to decrease the value of bricks to a particular value at each step, and the minimum value of any brick is 0 when all bricks are sold.
- We will set the variable maxProfit as 0 and the variable ptr as 1. maxProfit stores the maximum total profit, and ptr is a pointer to which we are decreasing the value of bricks having a value greater than the pointer value.
- Iterate till L is greater than 0
- Store total orders to reduce value of elements to ARR[ptr] and compare L with the value.
- If L is greater than total orders to reduce value of elements, then increment the maxProfit by profit to reduce brick’s cost to the ARR[ptr] and decrement L by the total orders.
- Otherwise, find the value val till which all elements will get decreased with the remaining L. If any order remaining after reducing the value of bricks to val, then choose brick with val cost for each transaction to the customer. Update maxProfit and set L as 0.
- Increment ptr by 1.
- Return the variable maxProfit.
The intuition behind the approach is to find the smallest number K such that the total number of bricks having cost more than K is smaller than L. After each transaction of a brick, the brick’s cost is decreased by 1, so our approach is trying to a minimum common value for all distinct bricks having a maximum cost till which value of bricks can be decreased efficiently, that value is K and Ninja could sell the bricks of a type till the cost of the brick remains more than K.
The variable low stores the value such that all bricks having cost more than low are sold to the customer. Iterate over the ARR to find the profit from all brick having cost more than low and increment answer by the profit attained by Ninja that is the profit obtained while reducing the value of the brick to low and decrement L the number of orders in which cost of the brick is greater than low and return the final answer.
Algorithm:
- We will set the variable maxProfit and low as 0 and the variable high with the maximum element in the ARR. maxProfit stores the maximum total profit. low stores the lowest value of brick.
- Iterate till low is less than or equal to high
- Take mid equal to (low + high)/2, if the number of bricks having cost more than mid is greater than L then set low as mid+1, otherwise set high as mid-1
- Now, the variable low stores the value such that all bricks having cost more than low are sold to the customer. Iterate index over 0 to the length of ARR and check if ARR[index] is greater than low
- Decrement L by the number of orders in which cost of brick that is ARR[index] is greater than low that is ARR[index]-low and increment maxProfit by the profit to reduce the cost of the brick, ARR[Index] to low.
- If L is greater than 0 then increment maxProfit by low for each of the remaining l transactions
- Return the variable maxProfit.
Similar problems