Sell diminishing valued colored balls

Array Math Binary Search Greedy Sorting Heap (Priority Queue)

30.1% acceptance

Feb 25, 2026

1152

402

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. You are given an integer array inventory, and an integer orders representing the total number of balls that the customer wants. Return the maximum total value modulo 10^9 + 7.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_profit(inventory: Vec<i32>, orders: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    const INV2: i64 = 500_000_004; // modular inverse of 2 mod MOD

    let arith_sum = |lo: i64, hi: i64| -> i64 {
      if lo > hi {
        return 0;
      }
      let n = (hi - lo + 1) % MOD;
      let s = (lo % MOD + hi % MOD) % MOD;
      n * s % MOD * INV2 % MOD
    };

    let mut inv: Vec<i64> = inventory.iter().map(|&x| x as i64).collect();
    inv.sort_unstable_by(|a, b| b.cmp(a));
    inv.push(0);
    let n = inv.len() - 1;
    let mut orders = orders as i64;
    let mut ans: i64 = 0;

    for i in 0..n {
      if inv[i] == inv[i + 1] {
        continue;
      }
      let height = inv[i] - inv[i + 1];
      let cols = (i + 1) as i64;
      let slab = cols * height;
      if orders >= slab {
        // Sell entire slab: all cols colors from level inv[i+1]+1 to inv[i]
        ans = (ans + cols % MOD * arith_sum(inv[i + 1] + 1, inv[i])) % MOD;
        orders -= slab;
      } else {
        // Partial: sell full_rows full levels, then remainder balls at floor
        let full_rows = orders / cols;
        let remainder = orders % cols;
        let floor = inv[i] - full_rows;
        ans = (ans + cols % MOD * arith_sum(floor + 1, inv[i])) % MOD;
        ans = (ans + remainder % MOD * (floor % MOD)) % MOD;
        break;
      }
      if orders == 0 {
        break;
      }
    }
    (ans % MOD) as i32
  }
}