2892. Minimizing Array After Replacing Pairs With Their Product π
Description
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
andy
, such thatx * y <= k
, and replace both of them with a single element with valuex * y
(e.g. in one operation the array[1, 2, 2, 3]
withk = 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.
Example 1:
Input: nums = [2,3,3,7,3,5], k = 20 Output: 3 Explanation: We perform these operations: 1. [2,3,3,7,3,5] -> [6,3,7,3,5] 2. [6,3,7,3,5] -> [18,7,3,5] 3. [18,7,3,5] -> [18,7,15] It can be shown that 3 is the minimum length possible to achieve with the given operation.
Example 2:
Input: nums = [3,3,3,3], k = 6 Output: 4 Explanation: We can't perform any operations since the product of every two adjacent elements is greater than 6. Hence, the answer is 4.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= 109
Solutions
Solution 1: Greedy
We use a variable $ans$ to record the current length of the array, and a variable $y$ to record the current product of the array. Initially, $ans = 1$ and $y = nums[0]$.
We start traversing from the second element of the array. Let the current element be $x$:
- If $x = 0$, then the product of the entire array is $0 \le k$, so the minimum length of the answer array is $1$, and we can return directly.
- If $x \times y \le k$, then we can merge $x$ and $y$, that is, $y = x \times y$.
- If $x \times y \gt k$, then we cannot merge $x$ and $y$, so we need to treat $x$ as a separate element, that is, $ans = ans + 1$, and $y = x$.
The final answer is $ans$.
The time complexity is $O(n)$, where n is the length of the array. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|