Skip to content

2892. Minimizing Array After Replacing Pairs With Their Product 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int minArrayLength(vector<int>& nums, int k) {
    int count = 0;
    long prod = -1;

    for (const int num : nums) {
      if (num == 0)
        return 1;
      if (prod != -1 && prod * num <= k) {
        prod *= num;
      } else {
        prod = num;
        ++count;
      }
    }

    return count;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int minArrayLength(int[] nums, int k) {
    int count = 0;
    long prod = -1;

    for (final int num : nums) {
      if (num == 0)
        return 1;
      if (prod != -1 && prod * num <= k) {
        prod *= num;
      } else {
        prod = num;
        count++;
      }
    }

    return count;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def minArrayLength(self, nums: list[int], k: int) -> int:
    count = 0
    prod = -1

    for num in nums:
      if num == 0:
        return 1
      if prod != -1 and prod * num <= k:
        prod *= num
      else:
        prod = num
        count += 1

    return count