Sell Diminishing-Valued Colored Balls - Practice Coding Problems

Sell Diminishing-Valued Colored Balls - Problem

Array Math Binary Search Greedy Sorting Heap (Priority Queue) Medium

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

Input & Output

Example 1 — Basic Case

$ Input: inventory = [2,5], orders = 4

› Output: 14

💡 Note: Sell balls with values 5, 4, 3, 2. Total = 5+4+3+2 = 14. We sell from color 1 (value 5), then 4, then 3, then from color 0 (value 2).

Example 2 — Multiple Colors

$ Input: inventory = [3,5], orders = 6

› Output: 19

💡 Note: Sell balls with values 5, 4, 3, 3, 2, 1. Total = 5+4+3+3+2+1 = 18. Wait, let me recalculate: 5+4+3+3+2+1 = 18. Actually: 5+4+3+3+2+2 = 19.

Example 3 — Large Numbers

$ Input: inventory = [1000000000], orders = 1000000000

› Output: 21

💡 Note: This would result in a very large number, so we return it modulo 10^9 + 7.

Constraints

1 ≤ inventory.length ≤ 10⁵
1 ≤ inventory[i] ≤ 10⁹
1 ≤ orders ≤ min(sum(inventory[i]), 10⁹)

Visualization

Tap to expand

Understanding the Visualization

Input

inventory=[2,5], orders=4 - we have 2 balls of color 0 and 5 balls of color 1

Greedy Strategy

Always sell from the color with highest current value

Output

Maximum revenue = 14 by selling balls with values 5,4,3,2

Key Takeaway

🎯 Key Insight: Use greedy approach - always sell the most valuable ball first to maximize revenue

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to always sell the most valuable ball first using a greedy approach. The optimal solution uses sort and group processing to handle balls in batches with arithmetic formulas. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Heap	O(orders × log n)	O(n)	Use a max heap to efficiently track and sell from the highest valued color
Sort and Group Processing	O(n log n + min(orders, max_value))	O(1)	Sort inventory and process balls in batches by grouping equal values
Brute Force - Sell One Ball at a Time	O(orders × n)	O(1)	Repeatedly find the color with maximum balls and sell one ball at a time

Greedy with Heap — Algorithm Steps

Build max heap from inventory
For each order: extract max, sell one ball, reinsert if positive
Sum all values sold

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Heap

Initialize max heap with inventory counts

Extract & Sell

Always extract maximum, sell ball, reinsert if positive

Repeat

Continue until all orders processed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void maxHeapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest])
        largest = left;
    
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        maxHeapify(arr, n, largest);
    }
}

int extractMax(int arr[], int* n) {
    int max = arr[0];
    arr[0] = arr[*n - 1];
    (*n)--;
    maxHeapify(arr, *n, 0);
    return max;
}

void insertHeap(int arr[], int* n, int value) {
    arr[*n] = value;
    int i = *n;
    (*n)++;
    
    while (i > 0 && arr[(i - 1) / 2] < arr[i]) {
        int temp = arr[i];
        arr[i] = arr[(i - 1) / 2];
        arr[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

int solution(int* inventory, int inventorySize, int orders) {
    const int MOD = 1000000007;
    long long result = 0;
    
    int heap[1000];
    int heapSize = 0;
    
    for (int i = 0; i < inventorySize; i++) {
        if (inventory[i] > 0) {
            insertHeap(heap, &heapSize, inventory[i]);
        }
    }
    
    for (int i = 0; i < orders; i++) {
        int maxCount = extractMax(heap, &heapSize);
        result = (result + maxCount) % MOD;
        
        if (maxCount > 1) {
            insertHeap(heap, &heapSize, maxCount - 1);
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int inventory[1000];
    int inventorySize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            inventory[inventorySize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int orders;
    scanf("%d", &orders);
    
    int result = solution(inventory, inventorySize, orders);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(orders × log n)

Each of 'orders' balls requires O(log n) heap operations

⚡ Linearithmic

Space Complexity

O(n)

Heap stores up to n colors

⚡ Linearithmic Space

28.6K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Heap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler