FastPrepFastPrep
Problem Brief

Compressing Array

FULLTIMEOA

Given an array of integers, a, in one operation one can select any two adjacent elements and replace them with their product. This operation can only be applied if the product of those adjacent elements is less than or equal to k.

The goal is to reduce the length of the array as much as possible by performing any number of operations. Return that minimum size.

Function Description

Complete the function getMinLength in the editor.

getMinLength has the following parameters:

  1. int a[n]: an array of integers
  2. int k: the constraint of the operation

Returns

int: the minimum length of the array after performing any number of operations

1Example 1

Input
a = [2, 3, 3, 7, 3, 5], k = 20
Output
3
Explanation
This is the list of operations that will give us the smallest array (1-based indexing):>
  • Merge the elements at indices (1, 2), resulting array will be - [6, 3, 7, 3, 5]
  • Merge the elements at indices (1, 2), resulting array will be - [18, 7, 3, 5]
  • Merge the elements at indices (3, 4), resulting array will be - [18, 7, 15]
    • Hence, the answer is 3.

    Constraints

    Limits and guarantees your solution can rely on.

    :>/code>
    public int getMinLength(int[] a, int k) {
  // write your code here
}
    Input

    a

    [2, 3, 3, 7, 3, 5]

    k

    20

    Output

    3

    Sign in to submit your solution.