Do one sequence if possible

Question

A sequence of integers is one sequence if the difference between any two consecutive numbers in this sequence is -1 or 1, and its first element is 0.

More precisely: a1, a2, ..., an is one sequence if:

For any k (1 ≤  k < n): |a[k] - a[k+1]|=1, 
a[1]=0

Given n and s ─ the sum of all elements in a. W it is necessary to build one sequence with the given parameters.

For example, if n = 8 and s = 4, then one of these sequences is [0 1 2 1 0 -1 0 1].

Please note that if for given n and s we cannot form such a sequence, we must also say that it is impossible. Otherwise, we need to report any of this sequence. How to do this, please help.

Answer 1

Here's a different approach to the aioobe algorithm, with formal proof of correctness.

For the sequence a (k), we define the difference sequence d (k) = a (k + 1) - a (k) and note that a (1) + a (2) + ... + a (n) = (n -1) d (1) + (n-2) d (2) + ... + 1d (n-1).

Theorem: for parameters n and s, there is a one-time single summation of length s in s if and only if (1) n (n-1) / 2 mod 2 = s mod 2 and (2) | s | ≤ n (n-1) / 2.

: n. , n = 1, . , d (k) & in; {± 1}, , (1), (2) , n-1 + n-2 +... + 1 = n (n-1)/2 -1 mod 2 = 1 mod 2. , , (1), (2). s ≥ 0, (n-1), s - (n-1). s < 0, (n-1), s + (n-1). (1), (2) (- ), , . / , , s ≥ 0/0 0 .

, Python.

def oneseq(n, s):
    assert isinstance(n, int)
    assert isinstance(s, int)
    nchoose2 = n*(n-1)//2
    abss = abs(s)
    if n < 1 or abss%2 != nchoose2%2 or abss > nchoose2: return None
    a = [0]
    for k in range(n-1, 0, -1):  # n-1, n-2, ..., 1
        d = 1 if s >= 0 else -1
        a.append(a[-1] + d)  # a[-1] equivalent to a[len(a) - 1]
        s -= k*d
    return a

Answer 2

-, , , . +1 -1 , , , ... , n , n . : ± (1 + 2 + 3 +... + n).

-, " " , (+1) (-1) node, , , .

+1, , -1, . , , . ""

    ", " + ", , ".

", " stepsLeft * previousValue.

.

solve(stepsLeft, prev, acc) {
    if stepsLeft == 0, return empty list  // base case
    ifIStayHere = acc + prev*stepsLeft
    step = ifIstayHere > s ? prev-1 : prev+1
    return [step] concatenated by solve(stepsLeft-1, step, acc+step)
}

, 0, stepsLeft = n-1.

, θ (n), , . ( Java.)