optimizing a non recursive algorithm of an integer sequence

Question

In an recruiting test platform , I had the following integer sequence problem that I solve it without a recursive function to avoid Stack Overflow :

Here's a short description of the problem :

We have a mark and at each stage we will move forward or backward. In stage 0 we are in position 0 (no steps) In stage 1 we take one step forward (+1 step) => position 1 For stage 2 we take two steps backward (-2 steps) => position -1 For stage n : the number of steps we took on the previous stage minus the number of steps we took on the the second-last stage, so on stage 3, we will have to take 3 steps backwards (-2 - 1). => position -4 etc...

The goal is to write the function int getPos(int stage) to return the position at the indicated stage.

with a pen and a paper I found this formula :

position (n) = steps (n-1) - steps (n-2) + position (n-1)

adnd here's my solution

#include <iostream>

using namespace std;

int getPos(int stage)
{
    if (stage < 2)
        return stage;

    if (stage == 2)
        return -1;

    int stepNMinus1 = -2;
    int stepNMinus2 = 1;
    int stepN = 0;
    int posNMinus1 = -1;
    int Res = 0;

    while (stage-- > 2)
    {
        stepN = stepNMinus1 - stepNMinus2;
        Res = stepN + posNMinus1;
        stepNMinus2 = stepNMinus1;
        stepNMinus1 = stepN;
        posNMinus1 = Res;
    }

    return Res;
}

int main()
{
    cout << "Pos at stage -1 = " << getPos(-1) << endl; // -1
    cout << "Pos at stage 0 = " << getPos(0) << endl; // 0
    cout << "Pos at stage 1 = " << getPos(1) << endl; // 1
    cout << "Pos at stage 2 = " << getPos(2) << endl; //-1
    cout << "Pos at stage 3 = " << getPos(3) << endl; // -4
    cout << "Pos at stage 4 = " << getPos(4) << endl; // -5
    cout << "Pos at stage 5 = " << getPos(5) << endl; // -3
    cout << "Pos at stage 100000 = " << getPos(100000) << endl; // -5
    cout << "Pos at stage 2147483647 = " << getPos(2147483647) << endl; // 1
}

After executing the test program via the platform test, the max value of an int case timed out the process and the test platform said that my solution is not optimized enough to handle some cases.

I tried the "register" keyword but it has no effect...

I'm really curious and I want to know how to write an optimized function .Should I change the algorithm (how ?) or use some compiler tunings ?

Answer 1

We will write the first stages

Stage    | Step   | Position
0        | 0      | 0
1.       | 1      |1
2        |-2      | -1
3        |-3      |-4
4        |-1      |-5
5        |2       |-3
6        |3       |0
7        |1       |1
8        |-2      |-1

We can see that in the step 6 is equal to step 0, step 1 = step 7, step 2 = step 7,...

So, for the step x the answer is step (x%6)

You can do

cout << "Pos at stage x = " << getPos((x%6)) << endl;