Final array state after k multiplication operations ii

Array Heap (Priority Queue) Simulation

13.1% acceptance

Feb 25, 2026

179

You are given an integer array nums, an integer k, and an integer multiplier. Perform k operations: find the minimum x (first occurrence), replace with x * multiplier. After k operations, apply modulo 109 + 7 to every value. Return the final state.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_final_state(nums: Vec<i32>, k: i32, multiplier: i32) -> Vec<i32> {
    let n = nums.len();
    let m = multiplier as i64;
    let k = k as i64;
    const MOD: i64 = 1_000_000_007;

    if m == 1 {
      // Multiplying by 1 never changes values; all exponents remain 0
      return nums.iter().map(|&x| ((x as i64) % MOD) as i32).collect();
    }

    let max0 = *nums.iter().max().unwrap() as i64;
    let mut exp = vec![0i64; n];

    // Min-heap: (current_value, original_index)
    let mut heap: std::collections::BinaryHeap<std::cmp::Reverse<(i64, usize)>> =
      (0..n).map(|i| std::cmp::Reverse((nums[i] as i64, i))).collect();

    // Phase 1: simulate until min >= max0 (original maximum) or k ops exhausted
    let mut k1 = 0i64;
    while k1 < k {
      let std::cmp::Reverse((val, idx)) = *heap.peek().unwrap();
      if val >= max0 {
        break;
      }
      heap.pop();
      let new_val = val * m;
      exp[idx] += 1;
      heap.push(std::cmp::Reverse((new_val, idx)));
      k1 += 1;
    }

    // Phase 2: remaining k2 = k - k1 ops distributed round-robin
    let k2 = k - k1;
    let q = k2 / n as i64;
    let r = k2 % n as i64;

    // Extract heap in sorted order (ascending by value, then by index)
    let mut sorted: Vec<(i64, usize)> =
      heap.into_iter().map(|std::cmp::Reverse(x)| x).collect();
    sorted.sort_unstable();

    for (pos, &(_, idx)) in sorted.iter().enumerate() {
      exp[idx] += q + if (pos as i64) < r { 1 } else { 0 };
    }

    // Compute result using modular exponentiation
    fn modpow(mut base: i64, mut e: i64, md: i64) -> i64 {
      base %= md;
      let mut result = 1i64;
      while e > 0 {
        if e & 1 == 1 {
          result = result * base % md;
        }
        base = base * base % md;
        e >>= 1;
      }
      result
    }

    (0..n)
      .map(|i| {
        let base_val = (nums[i] as i64) % MOD;
        let mult_factor = modpow(m % MOD, exp[i], MOD);
        ((base_val * mult_factor) % MOD) as i32
      })
      .collect()
  }
}