Minimized LCM Construction

Hi guys!

Today, we will see how to solve this problem:

You are given two positive integers n and x. Find an array of positive integers with length n and sum x that has minimum LCM.

Let's start with a simple brute force solution that creates every possible valid array and finds the minimum LCM:

void solve_1(int len, int sum, int cur, int& ans) {
    if (len == 0) {
        if (sum == 0) {
            ans = min(ans, cur);
        }
        return;
    }

    int rem = sum - len + 1;
    for (int val = 1; val <= rem; val++) {
        solve_1(len - 1, sum - val, lcm(val, cur), ans);
    }
}

int ans = x;
solve_1(n, x, 1, ans);

This solution is currently able to solve all valid inputs, constrained up to (x <= 25). In order to understand how to optimize it further let's see what kind of arrays it generates:

[1, 2, 2, 4]
[1, 2, 4, 2]
[4, 2, 1, 2]
[4, 2, 2, 1]

It's a case of (n, x) = (4, 9) and as you can see these are anagrams to each other. So, to remove these kind of duplicates we will only generate non-decreasing arrays and it's our first optimization. Next, let's see some more examples to understand what else we can do:

[9]
[1, 8]
[3, 3, 3]
[1, 2, 2, 4]
[1, 2, 2, 2, 2]

Here, one thing we can observe is that the LCM is always present and will be the maximum element of the array. What we are looking here is, say LCM is k and we replace every element with it then:

k * n >= x
k >= ceil(x / n)

Similarly, we can say that the upper bound of the answer will be:

v = floor(x / n);

[v, v, v + 1, v + 1] --> [1, 1, 2 * v, 2 * v]
[v, v, v, v + 1] --> [1, v, v, 2 * v]
[v, v + 1, v + 1, v + 1] --> [1, 2, v, 2 * v]

k <= 2 * v

Basically, we can always create a solution with this upper bound. And this is gonna be our second optimization. We will make sure in our recursion to only create the arrays that have lower LCM than our current answer which is initially our upper bound:

void solve_2(int len, int sum, int pre, int cur, int& ans) {
    if (len == 0) {
        if (sum == 0) {
            ans = min(ans, cur);
        }
        return;
    }

    for (int val = pre; val * len <= sum && val <= ans; val++) {
        int nxt = lcm(val, cur);
        if (val * len == sum) {
            ans = min(ans, nxt);
            continue;
        }
        if (nxt >= ans) continue;
        solve_2(len - 1, sum - val, val, nxt, ans);
    }
}

int upper = (x / n) * 2;
int ans = upper;
solve_2(n, x, 1, 1, ans);

With these two optimizations, we have improved the constrained on our algorithm to solve up to (x <= 150).

This is the best I can think of a recursively optimized solution. From here we start with an iterative solution, first let's take a look at an example:

k = lcm(a)
a = [divisor(k), divisor(k), k, k]

So, all of the array elements must be the divisor of k in order for k to be LCM. Then let's fix this k first and try to create an array with sum exactly x and length exactly n:

bool check_1(int len, int sum, int val) {
    vector<bool> dp(sum + 1);
    dp[0] = true;
    for (int i = 1; i <= len; i++) {
        vector<bool> tp(sum + 1);
        for (int j = 0; j < sum; j++) {
            if (dp[j]) {
                for (int divisor : divisors[val]) {
                    if (j + value > sum) break;
                    tp[j + value] = true;
                }
            }
        }
        dp = tp;
    }

    return dp[sum];
}

It's a dp to check if we can create a sum x by using exactly n divisors of k. The below example shows the dp indices marked as true during each iteration for (n, x, k) = (2, 6, 4) were:

[0] --> [1, 2, 4] --> [2, 3, 4, 5, 6, 8]

As 6 is present in final array so it's true that we can form it. Also as we have lower and upper bound on k so the range that we need to check is (x / n). So the current solution's time complexity will be:

O((x / n) * (x * n) * cbrt(x / n)) --> O(x * x * cbrt(x / n))

Now, you can say that this dp solution is somewhat like knapsack, but there is an issue that unlike a knapsack which doesn't have a constraint on the length of array you would have to create. So, here we need to modify our original representation of the array that we are creating:

k = lcm(a)
a = [divisor(k), divisor(k), k, k]
a_ = [k - divisor(k), k - divisor(k), 0, 0] --> [k - divisor(k), k - divisor(k)] --> [values(k), values(k)]
x_ = k * n - x

So, we will find this modified array with (length <= n). Let's say our initial array contains all elements as k, than this array b tells that for each index how much value you need to decrease from k to make it equal to sum x. Here, values represents:

values[k] = divisors[k];
values[k].pop_back();
reverse(values)

After this transformation, it becomes exactly a knapsack problem. Below represents one of the implementation of the knapsack:

vector<vector<int>> values;
vector<int> dist;

bool check_2(int len, int sum, int val) {
    int tot = min(sum, values[val].back() * (len / 2));
    fill(dist.begin(), dist.begin() + tot + 1, 0);

    queue<int> q;
    q.push(0);
    while (q.size()) {
        int cur = q.front();
        q.pop();

        if (2 * dist[cur] > len) continue;

        for (auto value : values[val]) {
            if ((sum - cur) % value == 0) {
                int can = (sum - cur) / value;
                if (can <= (len - dist[cur])) {
                    return true;
                }
            }
            if (value + cur <= tot && !dist[value + cur]) {
                dist[value + cur] = dist[cur] + 1;
                q.push(value + cur);
            }
        }
    }

    return false;
}

void solve_3(int len, int sum, int low, int& ans) {
    if (len * low == sum) return;

    for (int val = low; val <= sum; val++) {
        if (check_2(len, val * len - sum, val)) {
            ans = val;
            return;
        }
    }
}

for (int i = x; i >= 1; i--) {
    for (int j = 2 * i; j <= x; j += i) {
        values[j].push_back(j - i);
    }
}

int lower = ((x + n - 1) / n);
int ans = lower;
solve_3(n, x, lower, ans);

So, I forget to mention one important claim, i.e. in one of the optimal construction for this problem there is a pattern that a particular element is present in weak majority. What I mean is, if we have an optimal construction that doesn't full fill the above claim we can always transform it without breaking the constraint of (n, x, k). Below is one example of it:

// Transformation
[1, 1, 2, 4, 4] --> [2, 2, 2, 2, 4]

// Weak Majority
[1, 2, 4, 4]

Now, I didn't have a formal proof, but we can utilize this fact as when we are constructing our array we can perform a simple check that if the current element can be used for the rest of the array. After this check we have made sure that we can find an answer in just half of the original length n.

Time complexity of this approach is shown below: