Minimum cost to empty an array by repeatedly removing first and middle, first and last, or middle and last elements

user_7722745 0
Viewed 691

This question was asked to me in an interview, and I was unable to come up with an optimal solution.

Question

Given an even size array, we can perform any operation on the array, until the array becomes empty such that the overall cost should be minimum.

Operations:

  1. remove first and last element => cost will be gcd(first, last)
  2. remove first and middle element => cost will be gcd(first, middle)
  3. remove middle and last element => cost will be gcd(middle, last)

Note:

  • In an even size array, there are two middle elements. So, consider the second middle element as the middle element.
  • gcd(x,y) stands for Greatest Common Divisor between x and y

Example:

Input: [2, 4, 8, 6]

Output: 4

Explanation:

  • In the first operation remove the first and middle element, cost = gcd(2,8) = 2
  • In the second operation remove 4 and 6, cost = gcd(4,6) = 2
  • Total cost = 2+2 = 4
math language-agnostic arrays algorithm
1 Answers

Regardless of the order we perform the operations, the state of the list can be described with four pointers that describe exactly the two remaining, contiguous sections of the list.

These pointers are related by a specific set of rules that restrict which states are possible to achieve. I would start with using the four pointer combination and conduct recursion with memoised state.

We can reduce the state further by observing that the two contiguous sections can differ in length by either 0 or 2. I'll try to update this answer later.

JavaScript code (random test in Python against brute force available here):

function gcd(x, y){
  while(y)
    [x, y] = [y, x % y];
  return x;
}

function f(A){
  const memo = {};
  const n = A.length;
  const mid = n / 2;
  
  function g(l0, l1, r0, r1){
    const key = String([l0, l1, r0, r1]);

    if (memo.hasOwnProperty(key))
      return memo[key];
    
    const len_l = l1 - l0 + 1;
    const len_r = r1 - r0 + 1;

    if (len_l + len_r == 2){
      if (len_r && len_l)
        return gcd(A[l0], A[r0]);
      else if (len_l)
        return gcd(A[l0], A[l0 + 1]);
      else
        return gcd(A[r0], A[r0 + 1]);
    }

    let a = A[l0];
    let b = A[r1];

    const outer = gcd(a, b) + g(l0 + 1, l1, r0, r1 - 1);

    if (len_r >= len_l)
      var mid = r0 + (len_l + len_r) / 2 - len_l;
    else
      var mid = l0 + (len_l + len_r) / 2;

    b = A[mid];
    
    const _l1 = l1 - (mid == l1 ? 1 : 0);
    const _r0 = r0 + (mid == r0 ? 1 : 0);

    const left = gcd(a, b) + g(l0 + 1, _l1, _r0, r1);

    a = A[r1];

    const right = gcd(b, a) + g(l0, _l1, _r0, r1 - 1);

    return memo[key] = Math.min(outer, left, right);
  }
  
  return g(0, mid - 1, mid, n - 1);
}

let A = [2, 4, 8, 6];
console.log(JSON.stringify(A));
console.log(f(A));

A = [8,5,21,10,25,9]
console.log(JSON.stringify(A));
console.log(f(A));

const n = 200;
A = [];

for (let i=0; i<n; i++)
  A.push(i + 1);

console.log(JSON.stringify(A));
console.log(f(A));

user_20347870
Related