# 1648. Sell Diminishing-Valued Colored Balls
###### tags: `Binary Search`, `Amazon OA`

You have an `inventory` of different colored balls, and there is a customer that wants `orders` balls of **any** color.

The customer weirdly values the colored balls. Each colored ball's value is the number of balls **of that color** you currently have in your `inventory`. For example, if you own `6` yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only `5` yellow balls left, so the next yellow ball is then valued at `5` (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, `inventory`, where `inventory[i]` represents the number of balls of the `ith` color that you initially own. You are also given an integer `orders`, which represents the total number of balls that the customer wants. You can sell the balls **in any order**.

*Return the **maximum** total value that you can attain after selling `orders` colored balls.* As the answer may be too large, return it **modulo** `10^9 + 7`.

class Solution {
    public int maxProfit(int[] inventory, int orders) {
        int l = 0;
        int r = 1000000000;
        int mod = 1000000000 + 7;
        int m;
        
        while (l < r) {
            m = l + (r - l) / 2;
            if (isOrderRemain(inventory, orders, m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        
        // l = the value that deplete the order
        Long res = 0L;
        for (int i = 0; i < inventory.length; i++) {
            if (inventory[i] <= l) continue;
            res += ((long)inventory[i] + (long)l + 1) * ((long)inventory[i] - (long)l) / 2;
            orders -= inventory[i] - l;
        }
        
        res += (long)orders * (long)l;
        return (int)(res % mod);
    }
    
    private boolean isOrderRemain(int[] inventory, int orders, int m) {
        for (int i = 0; i < inventory.length && orders > 0; i++) {
            if (inventory[i] < m) continue;
            orders -= inventory[i] - m;
        }
        return orders > 0;
    }
}