I got this problem in an interview recently:

Given a set of numbers X = [X_1, X_2, ...., X_n] where X_i <= 500 for 1 <= i <= n. Increment the numbers (only positive increments) in the set so that each element in the set has a common divisor >=2, and such that the sum of all increments is minimized.

For example, if X = [5, 7, 7, 7, 7] the new set would be X = [7, 7, 7, 7, 7] Since you can add 2 to X_1. X = [6, 8, 8, 8, 8] has a common denominator of 2 but is not correct since we're adding 6 (add 2 to 5 and 1 to each of the 4 7's).

I had a seemingly working solution (as in it passed all the test cases) that loops through the prime numbers < 500 and for each X_i in X finds the closest multiple of the prime number greater than X_i.

function closest_multiple(x, y)
    return ceil(x/y)*y

min_increment = inf
for each prime_number < 500:
    total_increment = 0
    for each element X_i in X:
        total_increment  = closest_multiple(X_i, prime_number) - X_i
    min_increment = min(min_increment, total_increment)

return min_increment

It's technically O(n) but is there a better way to solve this? I've been suggested to use dynamic programming but am unsure how that would fit in here.

CodePudding user response：

Constant-bounded entries case

When X_i is bounded by a constant, the best time you can achieve asymptotically is O(n), since it takes at least that long to read all of your inputs. There are some practical improvements:

1. Filter out duplicates, so you work with a list of (element, frequency) pairs.
2. Early stopping in your loop.
3. Faster computation of closest_multiple(x, p) - x. This is slightly hardware/language dependent, but a single integer modulus op is almost certainly faster than an int -> float cast, float division, ceiling() call, and multiplication on the same magnitude numbers.

freq_counts <- Initialize-Counter(X) // List of (element, freq) pairs
min_increment = inf

for each prime_number < 500:
    total_increment = 0
    for each pair X_i, freq in freq_counts:
        total_increment  = (prime_number - (X_i % prime_number)) * freq
        if total_increment >= min_increment: break
    min_increment = min(min_increment, total_increment)

return min_increment

Large entries case

With uniformly chosen random data, the answer is almost always from using '2' as the divisor, and much larger prime divisors are vanishingly unlikely. However, let's solve for that worst case scenario.

Here, let max(X) = M, so that our input size is O(n (log M)) bits. We want a solution that's sub-exponential in that input size, so finding all primes below M (or even sqrt(M)) is out of the question. We're looking for any prime that gives us a min-total-increment; we'll call such a prime a min-prime. After finding such a prime, we can get the min-total-increment in linear time. We'll use a factoring approach along with two observations.

• Observation 1: The answer is always at most n, since the increment needed for the prime 2 to divide X_i is at most 1.

• Observation 2: We're trying to find primes that divide X_i or a number slightly larger than X_i for a large fraction of our entries X_i. Let Consecutive-Product-Divisors[i] be the set of all primes dividing either of X_i or X_i 1, which I'll abbreviate CPD[i]. This is exactly the set of all primes which divide X_i * (1 X_i).

• (Obs. 2 Continued) If U is a known upper bound on our answer (here, at most n), and p is a min-prime for X, then p must divide either X_i or X_i 1 for at least N - U/2 of our CPD entries. Use frequency counts on the CPD array to find all such primes.

Once you have a list of candidate primes (all min-primes are guaranteed to be in this list), you can test each one individually using your algorithm. Since a number k can have at most O(log k) distinct prime divisors, this gives O(n log M) possible distinct primes that divide at least half of the numbers
[X_1*(1 X_1), X_2*(1 X_2), ... X_n*(1 X_n)] that make up our candidate list. It's possible you can lower this bound with some more careful analysis, but it likely won't strongly affect the asymptotic runtime of the whole algorithm.

A more optimal complexity for large entries

The complexity of this solution is hard to write in short form, because the bottleneck is factoring n numbers of maximum size M, plus O(n^2 log M) arithmetic (i.e. addition, subtraction, multiply, modulo) operations on numbers of maximum size M. That doesn't mean the runtime is unknown: If you select any integer factoring algorithm and large-integer-arithmetic algorithms, you can derive the runtime exactly. Unfortunately, because of factoring, the best known runtime of the above algorithm is super-polynomial (but sub-exponential).

How can we do better? I did find a more complicated solution, based on Greatest Common Divisors (GCD) and dynamic-programming-like that runs in polynomial time (although likely much slower on non-astronomical-size inputs) since it doesn't rely on factoring.

The solution relies on the fact that at least one of the following two statements is true:

1. The number 2 is a min-prime for X, or
2. For at least one value of i, 1 <= i <= n there is an optimal solution where X_i remains unincremented, i.e. where one of the divisors of X_i produces a min-total-increment.

GCD-Based polynomial time algorithm

We can test 2 and all small primes quickly for their minimum costs. In fact, we'll test all primes p, p <= n, which we can do in polynomial time, and factor out these primes from X_i and its first n increments. This leads us to the following algorithm:

// Given: input list X = [X_1, X_2, ... X_n].
// Subroutine compute-min-cost(list A, int p) is 
// just the inner loop of the above algorithm.

min_increment = inf;
for each prime p <= n:
    min_increment = min(min_increment, compute-min-cost(X, p));

// Initialize empty, 2-D, n x (n 1) list Y[n][n 1], of offset X-values
for all 1 <= i <= n:
    for all 0 <= j <= n:
        Y[i][j] <- X[i]   j;

for each prime p <= n:  // Factor out all small prime divisors from Y
    for each Y[i][j]:
        while Y[i][j] % p == 0:
            Y[i][j] /= p;

for all 1 <= i <= n: // Loop 1
    // Y[i][0] is the test 'unincremented' entry
    // Initialize empty hash-tables 'costs' and 'new_costs'
    // Keys of hash-tables are GCDs,
    // Values are a running sum of increment-costs for that GCD

    costs[Y[i][0]] = 0;
    for all 1 <= k <= n: // Loop 2
        if i == k: continue;
        clear all entries from new_costs  // or reinitialize to empty
        for all 0 <= j < n: // Loop 3
            for each Key in costs: // Loop 4
                g = GCD(Key, Y[k][j]);
                if g == 1: continue;
                if g is not a key in new_costs:
                    new_costs[g] = j   costs[Key];
                else:
                    new_costs[g] = min(new_costs[g], j   costs[Key]);
        
        swap(costs, new_costs);
    if costs is not empty:
        min_increment = min(min_increment, smallest Value in costs);

return min_increment;

The correctness of this solution follows from the previous two observations, and the (unproven, but straightforward) fact that there is a list [X_1 r_1, X_2 r_2, ... , X_n r_n] (with 0 <= r_i <= n for all i) whose GCD is a divisor with minimum increment cost.

The runtime of this solution is trickier: GCDs can easily be computed in O(log^2(M)) time, and the list of all primes up to n can be computed in low poly(n) time. From the loop structure of the algorithm, to prove a polynomial bound on the whole algorithm, it suffices to show that the maximum size of our 'costs' hash-table is polynomial in log M. This is where the 'factoring-out' of small primes comes into play. After iteration k of loop 2, the entries in costs are (Key, Value) pairs, where each Key is the GCD of k 1 elements:
our initial Y[i][0], and [Y[1][j_1], Y[2][j_2], ... Y[k][j_k]] for some 0 <= j_l < n. The Value for this Key is the minimum increment sum needed for this divisor (i.e. sum of the j_l) over all possible choices of j_l.

There are at most O(log M) unique prime divisors of Y[i][0]. Each such prime divides at most one key in our 'costs' table at any time: Since we've factored out all prime divisors below n, any remaining prime divisor p can divide at most one of the n consecutive numbers in any Y[j] = [X_j, 1 X_j, ... n-1 X_j]. This means the overall algorithm is polynomial, and has a runtime below O(n^4 log^3(M)).

From here, the open questions are whether a simpler algorithm exists, and how much better than this bound can you achieve. You can definitely optimize this algorithm (including using the early-stopping and frequency counts from before). It's also likely that better bounds on counting large-and-distinct-prime-divisors for consecutive numbers shows this solution is already better than that stated runtime, but a simplification of this solution would be very interesting.