Maximal score after applying k operations

Array Greedy Heap (Priority Queue)

64.0% acceptance

Feb 25, 2026

878

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0. In one operation: choose an index i such that 0 <= i < nums.length, increase your score by nums[i], and replace nums[i] with ceil(nums[i] / 3). Return the maximum possible score you can attain after applying exactly k operations. The ceiling function ceil(val) is the least integer greater than or equal to val.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_kelements(nums: Vec<i32>, k: i32) -> i64 {
    use std::collections::BinaryHeap;
    let mut heap: BinaryHeap<i32> = nums.into_iter().collect();
    let mut score = 0i64;
    for _ in 0..k {
      if let Some(max) = heap.pop() {
        score += max as i64;
        heap.push((max + 2) / 3); // ceil(max / 3)
      }
    }
    score
  }
}