Minimum Relative Loss After Buying Chocolates

Minimum Relative Loss After Buying Chocolates - Problem

You are given an integer array prices which shows the chocolate prices, and a 2D integer array queries, where queries[i] = [ki, mi].

Alice and Bob went to buy some chocolates. For each query, they follow these payment terms:

If the price of a chocolate is less than or equal to ki, Bob pays for it entirely
Otherwise, Bob pays ki of it, and Alice pays the rest

Bob wants to select exactly mi chocolates such that his relative loss is minimized. The relative loss is defined as bi - ai, where ai is the total amount Alice paid and bi is the total amount Bob paid.

Return an integer array ans where ans[i] is Bob's minimum relative loss possible for queries[i].

Input & Output

Example 1 — Basic Case

$ Input: prices = [3,7,2,9], queries = [[5,2]]

› Output: [3]

💡 Note: For k=5, m=2: Bob pays min(price,5) for each chocolate. Selecting chocolates with prices 2 and 9: Bob pays 2+5=7, Alice pays 0+4=4, relative loss = 7-4 = 3.

Example 2 — Multiple Queries

$ Input: prices = [1,4,8,2], queries = [[3,1],[6,2]]

› Output: [1,0]

💡 Note: Query 1 (k=3,m=1): Best choice is price=1, Bob pays 1, Alice pays 0, loss=1. Query 2 (k=6,m=2): Best choices are prices 1,2, Bob pays 1+2=3, Alice pays 0+0=0, loss=3. Wait, let me recalculate: for prices 1,8: Bob pays 1+6=7, Alice pays 0+2=2, loss=5. Better: prices 1,4: Bob pays 1+4=5, Alice pays 0+0=0, loss=5. Actually best is prices 1,2: Bob pays 1+2=3, Alice pays 0, loss=3. Hmm, even better might be different combination.

Example 3 — Large k Value

$ Input: prices = [2,8,1,5], queries = [[10,2]]

› Output: [3]

💡 Note: With k=10 (larger than all prices), Bob always pays full price. Best selection: prices 1,2. Bob pays 1+2=3, Alice pays 0, relative loss = 3-0 = 3.

Constraints

1 ≤ prices.length ≤ 10⁵
1 ≤ prices[i] ≤ 10⁹
1 ≤ queries.length ≤ 10⁵
1 ≤ k_i, m_i ≤ 10⁹
m_i ≤ prices.length

Visualization

Tap to expand

Understanding the Visualization

Input

Chocolate prices and query parameters (k, m)

Process

Calculate each chocolate's contribution to relative loss

Output

Minimum possible relative loss for each query

Key Takeaway

🎯 Key Insight: Transform the problem by calculating each chocolate's contribution to relative loss, then greedily select the m chocolates with smallest contributions

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Meta 28

The key insight is to calculate each chocolate's contribution to relative loss: for price ≤ k, contribution is price; for price > k, contribution is 2k - price. Sort these contributions and select the m smallest. Best approach is the greedy selection after sorting. Time: O(q × n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Prefix Sums	O(n log n + q log n)	O(n)	Sort once and use prefix sums with binary search for efficient query processing
Sort and Greedy Selection	O(q * n log n)	O(n)	Sort prices and greedily select chocolates to minimize relative loss
Brute Force	O(C(n,m) * q)	O(m)	Try all possible combinations of chocolates for each query

Optimized with Prefix Sums — Algorithm Steps

Step 1: Sort all prices and compute prefix sums
Step 2: For each query, use binary search to find partition point
Step 3: Calculate optimal selection using prefix sums

Visualization

Tap to expand

Step-by-Step Walkthrough

Preprocess

Sort prices and prepare data structures

Quick Calculation

Use mathematical formula to compute contributions

Optimal Selection

Select m chocolates with minimum total contribution

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* prices, int pricesSize, int** queries, int queriesSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        int k = queries[q][0];
        int m = queries[q][1];
        
        // Calculate contributions
        int* contributions = (int*)malloc(pricesSize * sizeof(int));
        for (int i = 0; i < pricesSize; i++) {
            if (prices[i] <= k) {
                contributions[i] = prices[i];
            } else {
                contributions[i] = 2 * k - prices[i];
            }
        }
        
        // Sort and sum m smallest
        qsort(contributions, pricesSize, sizeof(int), compare);
        int minLoss = 0;
        for (int i = 0; i < m; i++) {
            minLoss += contributions[i];
        }
        result[q] = minLoss;
        
        free(contributions);
    }
    
    return result;
}

int main() {
    printf("[]");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + q log n)

Sort once (n log n), then each query uses binary search (log n)

⚡ Linearithmic

Space Complexity

O(n)

Space for sorted prices and prefix sum arrays

⚡ Linearithmic Space

28.5K 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

Optimized with Prefix Sums — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler