Find minimum cost to convert array to arithmetic progression

Question

I recently encountered this question in an interview. I couldn't really come up with an algorithm for this.

Given an array of unsorted integers, we have to find the minimum cost in which this array can be converted to an Arithmetic Progression where a cost of 1 unit is incurred if any element is changed in the array. Also, the value of the element ranges between (-inf,inf).

I sort of realised that DP can be used here, but I couldn't solve the equation. There were some constraints on the values, but I don't remember them. I am just looking for high level pseudo code.

Answer 1

EDIT Here's a correct solution, unfortunately, while simple to understand it's not very efficient at O(n^3).

function costAP(arr) {
    if(arr.length < 3) { return 0; }
    var minCost = arr.length;
    for(var i = 0; i < arr.length - 1; i++) {
        for(var j = i + 1; j < arr.length; j++) {
            var delta = (arr[j] - arr[i]) / (j - i);
            var cost = 0;
            for(var k = 0; k < arr.length; k++) {
                if(k == i) { continue; }
                if((arr[k] + delta * (i - k)) != arr[i]) { cost++; }
            }
            if(cost < minCost) { minCost = cost; }
        }
    }
    return minCost;
}

• Find the relative delta between every distinct pair of indices in the array
• Use the relative delta to test the cost of transforming the whole array to AP using that delta
• Return the minimum cost

Answer 2

Louis Ricci had the right basic idea of looking for the largest existing arithmetic progression, but assumed that it would have to appear in a single run, when in fact the elements of this progression can appear in any subset of the positions, e.g.:

1 42 3 69 5 1111 2222 8

requires just 4 changes:

  42   69   1111 2222
1    3    5           8

To calculate this, notice that every AP has a rightmost element. We can suppose each element i of the input vector to be the rightmost AP position in turn, and for each such i consider all positions j to the left of i, determining the step size implied for each (i, j) combination and, when this is integer (indicating a valid AP), add one to the the number of elements that imply this step size and end at position i -- since all such elements belong to the same AP. The overall maximum is then the longest AP:

struct solution {
    int len;
    int pos;
    int step;
};

solution longestArithProg(vector<int> const& v) {
    solution best = { -1, 0, 0 };

    for (int i = 1; i < v.size(); ++i) {
        unordered_map<int, int> bestForStep;
        for (int j = 0; j < i; ++j) {
            int step = (v[i] - v[j]) / (i - j);
            if (step * (i - j) == v[i] - v[j]) {
                // This j gives an integer step size: record that j lies on this AP
                int len = ++bestForStep[step];
                if (len > best.len) {
                    best.len = len;
                    best.pos = i;
                    best.step = step;
                }
            }
        }
    }

    ++best.len;     // We never counted the final element in the AP
    return best;
}

The above C++ code uses O(n^2) time and O(n) space, since it loops over every pair of positions i and j, performing a single hash read and write for each. To answer the original problem:

int howManyChangesNeeded(vector<int> const& v) {
    return v.size() - longestArithProg(v).len;
}