Minimizing array after replacing pairs with their product

Array Dynamic Programming Greedy

40.7% acceptance

Mar 31, 2026

Given an integer array nums and an integer k, you can perform the following operation on the array any number of times: Select two adjacent elements of the array like x and y, such that x * y <= k, and replace both of them with a single element with value x * y (e.g. in one operation the array [1, 2, 2, 3] with k = 5 can become [1, 4, 3] or [2, 2, 3], but can't become [1, 2, 6]). Return the minimum possible length of nums after any number of operations.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_array_length(nums: Vec<i32>, k: i32) -> i32 {
    if nums.iter().any(|&x| x == 0) {
      return 1;
    }
    let n = nums.len();
    if n == 0 {
      return 0;
    }
    let k = k as i64;
    let mut count = 1;
    let mut product = nums[0] as i64;
    for i in 1..n {
      let x = nums[i] as i64;
      if product * x <= k {
        product *= x;
      } else {
        count += 1;
        product = x;
      }
    }
    count
  }
}