1648. Sell Diminishing-Valued Colored Balls #

Problem #

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 109 + 7.

Example 1:

Input: inventory = [2,5], orders = 4
Output: 14
Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.

Example 2:

Input: inventory = [3,5], orders = 6
Output: 19
Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.

Example 3:

Input: inventory = [2,8,4,10,6], orders = 20
Output: 110

Example 4:

Input: inventory = [1000000000], orders = 1000000000
Output: 21
Explanation: Sell the 1st color 1000000000 times for a total value of 500000000500000000. 500000000500000000 modulo 109 + 7 = 21.

Constraints:

• 1 <= inventory.length <= 10^5
• 1 <= inventory[i] <= 10^9
• 1 <= orders <= min(sum(inventory[i]), 10^9)

Problem Summary #

You have an inventory of balls, inventory, containing balls of different colors. A customer wants a total of orders balls of any color. This customer has a special way of valuing the balls: each ball’s value is the current number of remaining balls of the same color. For example, if there are 6 yellow balls left, then when the customer buys the first yellow ball, its value is 6. After this transaction, only 5 yellow balls remain, so the next yellow ball has a value of 5 (that is, the value of balls decreases as the customer buys more balls of the same color).

You are given an integer array inventory, where inventory[i] represents the initial number of balls of the ith color. You are also given an integer orders, which represents the total number of balls the customer wants to buy. You can sell the balls in any order. Return the maximum total value after selling orders balls. Since the answer may be very large, return the result modulo 109 + 7.

Constraints:

• 1 <= inventory.length <= 10^5
• 1 <= inventory[i] <= 10^9
• 1 <= orders <= min(sum(inventory[i]), 10^9)

Solution Thought Process #

• Given an inventory array and orders operations, the task is to output the sum of the largest orders elements in the array. Note that every time an element inventory[i] is added to the sum, that element decreases by one. The next time we add again, we need to choose the maximum value of the updated array.

• After seeing this problem, it is easy to think of using a priority queue. Build a max heap, pop the current maximum value maxItem, add it to the result, then decrement maxItem by one and push it back. After repeating this loop orders times, we get the final result. This is indeed what the problem means, but we cannot write the code this way because the constraints give the size of orders. The maximum value of orders is 10^9. This priority queue approach will definitely time out, with a time complexity of O(orders⋅logn). So we need another idea. In the priority queue approach, the operation is repeated orders times, but among these operations, some are unnecessary redundant operations. These numerous “wasted” operations cause the timeout. Consider whether, among the orders operations, we can merge n pop operations and first pop the top n largest numbers in one go. This is feasible, because every time an element is popped, it only decreases by one, which is very regular.

• To make the following description clearer and easier to understand, we also need to define one more value: thresholdValue, which is the maximum value of the current inventory array after performing the operation n times. Regarding the understanding of thresholdValue, note that thresholdValue can come from two sources: one is that the value already exists in the original array, and the other is that an inventory[i] element decreases to thresholdValue. For example: the original array is [2,3,3,4,5], and orders = 4. After taking 4 times, the remaining array is [2,2,3,3,3]. Among the three 3s, one of them comes from 4-1=3, or from 5-2=3.

• Use binary search in the interval [0, max(inventory)] to find this thresholdValue, the minimum thresholdValue that satisfies the following inequality: \[ \sum_{inventory[i]\geqslant thresholdValue}^{} \left ( inventory[i] - thresholdValue \right )\leqslant orders \] The smaller thresholdValue is, the larger the value on the left side of the inequality is. As thresholdValue increases, the value on the left side becomes smaller and smaller, until it just becomes less than or equal to orders. After finding thresholdValue, we still need to determine how many values are equal to thresholdValue - 1.

  

• Using the example above again, the original array is [2,3,3,4,5], and orders = 4. We can obtain thresholdValue = 3. The part where inventory[i] > thresholdValue must be taken 100%. thresholdValue is like a water level: everything above the water level must be taken away, and the values in each column can be calculated using the arithmetic sequence sum formula. But orders - thresholdValue = 1, which means one more ball below the water level needs to be taken, namely one arbitrary ball among the 4 balls inside the dashed box below the thresholdValue line. The final total result is the sum of these 2 parts, ( ( 5 + 4 ) + 4 ) + 3 = 16.

Code #

package leetcode

import (
	"container/heap"
)

// Solution 1 Greedy + Binary Search
func maxProfit(inventory []int, orders int) int {
	maxItem, thresholdValue, count, res, mod := 0, -1, 0, 0, 1000000007
	for i := 0; i < len(inventory); i++ {
		if inventory[i] > maxItem {
			maxItem = inventory[i]
		}
	}
	low, high := 0, maxItem
	for low <= high {
		mid := low + ((high - low) >> 1)
		for i := 0; i < len(inventory); i++ {
			count += max(inventory[i]-mid, 0)
		}
		if count <= orders {
			thresholdValue = mid
			high = mid - 1
		} else {
			low = mid + 1
		}
		count = 0
	}
	count = 0
	for i := 0; i < len(inventory); i++ {
		count += max(inventory[i]-thresholdValue, 0)
	}
	count = orders - count
	for i := 0; i < len(inventory); i++ {
		if inventory[i] >= thresholdValue {
			if count > 0 {
				res += (thresholdValue + inventory[i]) * (inventory[i] - thresholdValue + 1) / 2
				count--
			} else {
				res += (thresholdValue + 1 + inventory[i]) * (inventory[i] - thresholdValue) / 2
			}
		}
	}
	return res % mod
}