How to find a set of ascending natural numbers which when added to another set of ascending natural numbers sums to a certain number

Question

Given: $$ X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1} $$ $$ z \in \mathbb N $$

Wanted result: $$ Y = \left\{ y_1, y_2, \ldots , y_n \right\}\text{ with }y_i \in \mathbb N and 0 \le y_i \le y_{i+1}\text{ and }(x_i-y_i) \le (x_{i+1}-y_{i+1}) $$

Where: $$ \sum \limits_{i=0}^n (x_i-y_i) = z $$

For example:

$X = \{1, 5, 50\}$, $z = 8$

Then the result would be: $Y = \{0, 2, 46\}$ because $X - Y$ (component wise) $= \{1, 3, 4\}$. $1+3+4=8$.

Is there a efficient solution to this problem?

Answer 1

I have implemented a solution in javascript if anybody is interested:

function findOptimalDistribution(Z, z) {
    // Make a working copy
    var Y = Z.slice(0);

    // Add dummy element so the 'lowest' value is 1, increment z accordingly
    Y.unshift(1);
    z++;

    // calculate sum of Y
    var R = 0;
    for(var i = 0; i < Y.length; i++) {
        R += Y[i];
    }

    // R contains the remaining 'overlap' over z
    R -= z;

    // R <= 0 means the condition is already fullfiled
    if (R <= 0) {
        return Y.slice(1);
    }

    for(var i = Y.length - 1, u = 1; i > 0; i--, u++) {
        var c = (Y[i] - Y[i - 1]);

        var b = (R <= c*u);
        if (b) {
            c = Math.floor(R / u);
        }

        for(var j = Y.length - 1; j >= i; j--) {
            Y[j] -= c;
        }
        R -= c * u;

        // Subtract the remainder of R, that got 'lost' due to rounding (Math.floor)
        if (b) {
            for (var j = i; j < i + R; j++) {
                Y[j]--;
            }

            R = 0;
        }

        if (R == 0) {
            break;
        }
    }

    return Y.slice(1);
}

This takes $X$ and $z$ as parameters and returns $X - Y$.

Here also a working example: http://jsfiddle.net/ujQh7/2/

Answer 2

There are more solutions. Do you insist that the $x_i-y_i$ be monotonic as well? It appears you accept $0 \in \Bbb N$, so $Y$ could be $\{0,0,48\}, \{0,3,45\},\{1,1,46\}$ or many others.

Answer 3

You have: $\sum\limits_{i=1}^{n}x_i-z=\sum\limits_{i=1}^{n}y_i$.

Hence, you are looking for a vector $y$ in $\mathbb{N}^{n}$ sorted in the ascending order such that $\sum\limits_{i=1}^{n}y_i=z^{\prime}$, where $z^{\prime}=\sum\limits_{i=1}^{n}x_i-z$=constant.

Therefore there exist many $y$. You can choose the elements of $y$ arbitrarily as you want such that $y_i\leq y_{i+1}\;\forall\;i$. In your example, I can choose $y=\{0, 1, 47\}$ or $\{0, 6, 42\},\;\dotsc$