Problem Statement

You are given an array containing integers nums and an integer value k. You can perform the below operation on the array elements for multiple times:

• Pick two adjacent elements, x and y, from nums and replace them with a single element equal to their product, x*y, but only if x*y is less than or equal to k.

Return the minimum possible length of nums after performing multiple operations.

Examples

• Example 1:

  • Input: nums = [2, 3, 4, 5], k = 10
  • Expected Output: 3
  • Justification: We can replace 2 and 3 with their product 6 ([6, 4, 5]). No further operations can be performed since all adjacent products will exceed k. Hence, the minimum length is 3.

• Example 2:

  • Input: nums = [1, 2, 2, 3], k = 5
  • Expected Output: 2
  • Justification: First, replace 2 and 2 with 4 ([1, 4, 3]), then replace 1 and 4 with 4 ([4, 3]). No more operations can be performed, resulting in a minimum length of 2.

• Example 3:

  • Input: nums = [10, 5, 2, 3, 4, 2, 20, 1], k = 50
  • Expected Output: 3
  • Justification: First, replace 10 and 5 with 50 ([50, 2, 3, 4, 2, 20, 1]), then replace 2, 3, 4 and 2 with 48 ([50, 48, 20, 1]), and then replace 20 and 1 with 20 ([50, 48, 20]). No more operations can be performed, resulting in a minimum length of 3.

Try it yourself

Try solving this question here: