2892. Minimizing Array After Replacing Pairs With Their Product

If there is a zero in the array, then the answer would be 1.

Merge all adjacent ones (since 1 * 1 = 1 and k >= 1).

Let dp[i] be the answer to the problem for the first i elements.

To calculate dp[i], try to brute-force all indices j such that elements from j to i are merged together to create a new element.

For a fixed i, you could go backward from ith elements and multiply them together until the product is at most k. Now if you are currently on index j and you've merged all elements from jth element to ith element, dp[i] = min(dp[i], dp[j - 1] + 1).

The above backward moving can be done at most 2 * log2(k) times. Since we've merged adjacent ones, every two adjacent elements have a product of at least 2.

So the total time complexity would be n * 2 * log2(k).