Minimize array elements by multiplying adjacent elements only if the product is less than equal to k

Question

I recently came across this question in an online assessment.

arr = [2,6,2,4] 
k = 15

The array elements need to be minimized by multiplying two adjacent elements only and only if their product is less than k.

Example:

(2,6,2,4)
(2*6,2*4) --> since 12 and 8 are less than k which is 15
(12,8)

The following pattern could have also been followed:

(2,6,2,4)
(2,6*2,4) 
(2,12,4) --> no . of  elements is 3 which is more than 2 thus non-optimal.

I have been stuck on this problem for days.

I tried walking it through the Matrix Chain Multiplication problem, but I am unable to make any headway. The main difference is that in the MCM problem all matrices CAN BE multiplied with each other. There is no case where 2 matrices cannot be multiplied.

Any hints ?

Answer 1

As the values of the array are strictly positive, you can use a greedy algorithm: keep multiplying values until a next multiplication would be k or more. When that happens, start a new chunk and reset the product to the current array value. This way we put the chunk boundaries as far to the right as possible. We can see that if we would move one chunk boundary more to the left, this would never decrease the number of chunks needed.

Here is an implementation of this greedy algorithm in (simple) JavaScript:

function solve(arr, k) {
    if (arr.length == 0) return 0; // Boundary case
    
    let product = 1;
    let count = 1;
    
    for (let i = 0; i < arr.length; i++) {
        product = product * arr[i];
        if (product >= k) { // Start a new chunk
            product = arr[i];
            count++;
        }
    }
    return count;
}

// Example run
const arr = [2,6,2,4]; 
const k = 15;
const result = solve(arr, k);
console.log("Number of chunks", result);

If we would allow 0 as possible array value, and k is strictly positive, then the occurrence of a zero would lead to the result 1: all values can be multiplied to one product which is 0.

This algorithm would no longer work correctly if negative array values would be allowed.