We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sell Diminishing-Valued Colored Balls

Difficulty: Medium

Problem Description

You have an inventory of different colored balls, and there is a customer that wants orders balls of any color. Each colored ball's value is the number of balls of that color you currently have in your inventory. The customer weirdly values the colored balls. Return the maximum total value that you can attain after selling orders colored balls. The answer may be too large, so return it modulo 10^9 + 7.

Key Insights

  • The value of the balls decreases as you sell more of a specific color.
  • To maximize the total value, sell the most abundant balls first.
  • Use a max-heap (priority queue) to efficiently get the color with the highest number of balls.
  • As you sell from the color with the highest count, adjust the count and continue selling until all orders are fulfilled.

Space and Time Complexity

Time Complexity: O(n log n) where n is the number of different colors (due to heap operations).
Space Complexity: O(n) for storing the max-heap.

Solution

To solve this problem, we can use a max-heap to always sell the balls with the highest value first. By utilizing this data structure, we can efficiently extract the maximum ball count, sell one ball, and decrease the count. We sum the values obtained from each sale until we fulfill the total orders. Finally, we return the total modulo 10^9 + 7.

Code Solutions

import heapq

def maxProfit(inventory, orders):
    MOD = 10**9 + 7
    max_heap = [-x for x in inventory]  # Using negative values to simulate max-heap
    heapq.heapify(max_heap)
    
    total_value = 0
    while orders > 0:
        max_balls = -heapq.heappop(max_heap)  # Get the color with the maximum balls
        total_value += max_balls  # Sell one ball
        orders -= 1  # Decrease the number of orders
        
        next_balls = max_balls - 1  # The next value after selling one
        if next_balls > 0:
            heapq.heappush(max_heap, -next_balls)  # Push updated count back into heap

    return total_value % MOD
← Back to All Questions