Proof: Find minimum moves to reach target on an infinite line algorithm An infinite line is given, where we stand at $0$, and we can move by a distance of $i$ units to left or right in our $i$-th step: we need to find the minimum number of steps needed to reach a particular target.
The algorithm I found is the following one:
target = abs(target); 
int sum = 0, step = 0; 
while (sum < target || (sum - target) % 2 != 0) { 
        step++; 
        sum += step; 
    } 
return step; 

I do not know if the algorithm works mathematically. For example, I do know that for $i=11$ it gives the answer $5$, which is correct, but what is the mathematics behind it?
 A: You are given an integer $T$ (=target) and you are looking for the smallest number $n$ such that $\pm 1\pm2\pm\ldots\pm n=T$.
What the algorithm is doing is this: first it assumes $T$ is positive (because the solution is the same for $T$ and $-T$ - that is the purpose of target = abs(target)). Then it finds the smallest sum $S_n=1+2+\ldots+n$ that satisfies two conditions:

*

*$S_n\ge T$

*$S_n$ is of the same parity as $T$.

Then it outputs the value $n$.
Examples
Let's set $T=11$. The smallest sum $1+2+\ldots+n$ that is not smaller than $11$ is $1+2+3+4+5=15$. We have obviously "overshot" $11$, but by a suitable change in signs we will get $11$ as, say $1-2+3+4+5=11$.
Let's now set $T=12$. The smallest sum is still $1+2+3+4+5=15$ but it is of the wrong parity. Changing pluses into minuses will preserve the parity, so none of $\pm 1\pm 2\pm 3\pm 4\pm 5$ can be equal $12$. We can go further to $1+2+3+4+5+6=21$ but this sum is also odd. Only $1+2+3+4+5+6+7=28$ is of the correct parity (even). Now, we have "overshot" $12$, but we can now change some of the plus signs into minus, in hope that we can reach the sum of $12$. Indeed, this is possible as $-1+2+3+4+5+6-7=12$.
This is the precise motivation for the algorithm you've shown. First, "overshoot" the target, using a sum $1+2+\ldots+n$ of the right parity (the parity of $T$), and then prove that we can change some of the plus signs to minus to get the correct sum.
Proof: To prove that this algorithm is correct, one needs to prove that the above two conditions ($S_n\ge T$, $S_n$ of the same parity as $T$) are sufficient and necessary to be able to write $T$ as a sum of the form $\pm 1\pm 2\pm\ldots\pm n$. Necessity is easy to see:

*

*If $S_n<T$ then, obviously, the biggest sum $1+2+\ldots+n<T$ and it cannot be made any bigger by converting some pluses into minuses.

*If $S_n$ and $T$ are of different parity, then no way of putting pluses and minuses can convert the sum $S_n=1+2+\ldots+n$ into $T$. Namely, every conversion of $+i$ into $-i$ changes the sum by $2i$ - by an even number. Thus all the numbers of the form $\pm 1\pm 2\pm\ldots\pm n$ are of the same parity, and if one of them (the $S_n$ itself) is not of $T$'s parity - none of them is!

Now, for sufficiency: assume that $S_n=1+2+\ldots+n\ge T$ and is of the same parity as $T$. We need to prove that there is some ordering of $+$ and $-$ signs that convert this sum to exactly $T$. In other words, we need something like:
Lemma: If $S_n=1+2+\ldots+n$, then every number $T, 0\le T\le S_n$ of the same parity as $S_n$ can be represented in at least one way as a sum $\pm 1\pm 2\pm\ldots\pm n$.
Proof: Induction on $n$:
Trivial edge case: $n=0$, $S_0=0$ (empty sum). This is true because the only $T$ satisfying those conditions is $T=0$, but in that case $T=S_0$.
Inductive step: $n-1\to n$. Let $n\ge 1$ and let $0\le T\le S_n$ of the same parity as $S_n$. Then, either $T-n$ or $n-T$ will be between $0$ and $S_{n-1}$:

*

*If $T\ge n$, then $0\le T-n\le S_n-n=S_{n-1}$.

*If $0\lt T\le n$, then $0\le n-T\le n-1\le S_{n-1}$.

*The only remaining case is $T=0$, in which case $n-T=n\le S_{n-1}$ for all $n\ge 3$. The cases $n=1,2$ are impossible because $T=0$ is not of the same parity as either $S_1=1$ or $S_2=3$.

Also, $T-n$ and $n-T$ are of the same parity, i.e. both of the same parity as $S_n-n=S_{n-1}$.
Now, we can apply the inductive hypothesis to either $T-n$ or $n-T$, as at least one of them satisfy the required conditions:

*

*Either $T-n=\pm 1\pm 2\pm \ldots\pm (n-1)$, in which case $T=\pm 1\pm 2\ldots\pm (n-1)+n$

*Or $n-T=\pm 1\pm 2\pm\ldots\pm(n-1)$, in which case $T=\mp 1\mp 2\mp\ldots\mp (n-1)+n$.

