Time limit exceeded in a number of steps game

Question

I'm trying to solve the following interviewbit question:

Given a target A on an infinite number line, i.e. -infinity to +infinity.

You are currently at position 0 and you need to reach the target by moving according to the below rule:

In ith move you can take i steps forward or backward. Find the minimum number of moves required to reach the target.

Input Format First and only argument is an integer A.

Output Format Return an integer denoting the minimum moves to reach target.

My code:

int solve(int A) {
    int B=0;
    int i =1;
    int count =0;
    
    if(A<0){
        A = A*(-1);
    }

    while(A!=B)
    {
        if(A>(B+i)){
            count++;
            B=B+i;
            i++;
        }
        else if(A<(B+i)){
            count++;
            B=B-i;
            i++;
        }
    }
    return count;
}

It always give time limit exceeded error. I'm trying to understand how to avoid that, but couldn't find anything.

Answer 1

You're being asked to find the smallest n such that ±1±2±3±...±n = A.

Let T(N) = 1+2+...+N.

Assume A is positive (otherwise negate it). Let N be the smallest integer such that T(N) = 1+2+...+N >= A.

• If T(N) = A, then the solution is N.
• If T(N) - A is even, then the solution is still N (change the sign of (T(N)-A)/2 in 1+2+...+N).
• If T(N) - A is odd and N is even, then the solution is N+1 (change the sign of (T(N)+N+1-A)/2 in 1+2+...+N+(N+1)).
• If T(N) - A is odd and N is odd, then the solution is N+2 (change the sign of (T(N)+1-A)/2 in 1+2+...+N-(N+1)+(N+2)).

It's easy to see that these solutions are optimal: the solution in each case is the smallest n such that T(n)>=A and T(n)-A is even (T(n)-A is odd is impossible, because ±1±2±3±...±n - A is odd (and hence not 0) when T(n)-A is odd).

You can find the smallest N with T(N) >= A by solving a quadratic equation (since T(N)=N(N+1)/2).

An example for each case:

• A=10. T(4)=10, T(4)=A so the the answer is 4: 1+2+3+4=10.
• A=11. T(5)=15. T(5)-11=4 is even, so the answer is 5: 1-2+3+4+5=11.
• A=9. T(4)=10. T(4)-9=1 is odd, but N is even, so the answer is 5: 1+2-3+4+5=9.
• A=12. T(5)=15. T(5)-12=3 is odd, and N is odd, so the answer is 7: 1-2+3+4+5-6+7=12.

A solution will look something like this (untested):

A = abs(A);
int N = ceil((sqrt(8*A + 1) - 1) / 2);
if ((N*(N+1)/2 - A) % 2) ++N;
if ((N*(N+1)/2 - A) % 2) ++N;
printf("%d\n", N);

Or you can write a simpler version that runs in sqrt(A) time:

int N=1;
while (N*(N+1)/2 < abs(A) || (N*(N+1)/2 - abs(A)) % 2) N++;
printf("%d\n", N);