Dancer.GetPositionAt(int n)

 Let's learna new dance! the first thing you need to know is that you can only move forward or backward. When moving backward, your number of steps will be negative. This dance require every performer to follow a precise sequence of steps: stage 0: first, get away from obstacles by setting up your starting point at position 0; stage 1: take one step forward (+1 step); stage 2: take two steps backward (-2 steps) to follow, the steps as well as the direction you will have to take in your next move will each time be obtained thanks to a specific calculation: the number of steps you took on the previous stage minus the number of steps you took on the penultimate stage (the second - last stage). That is on stage 3, a dancer will have to take 3 steps backward (-2-1). Implementer en c# the methode int Dancer.GetPositionAt(int n) to return the dancer's position at stage n. input: 0<= n <= 2147483647. important note: try to saave memory space and cpu cycles if possible. Exemples: n = 3 return -4; n = 100000 return -5 ; n = 2147483647 return 1.

This is a linear recurrence problem:

• Stage 0 → 0 (starting position)

• Stage 1 → +1

• Stage 2 → -2

• Stage n ≥ 3 → step_n = step_(n-1) − step_(n-2)

The dancer’s position at stage n is the sum of all previous steps.

---

Step 1: Understanding the sequence

Let’s compute the first few steps:

n	step_n	position
0	0	0
1	+1	0 + 1 = 1
2	-2	1 + (-2) = -1
3	-2 - 1 = -3	-1 + (-3) = -4
4	-3 - (-2) = -1	-4 + (-1) = -5
5	-1 - (-3) = 2	-5 + 2 = -3
6	2 - (-1) = 3	-3 + 3 = 0
7	3 - 2 = 1	0 + 1 = 1
8	1 - 3 = -2	1 + (-2) = -1
9	-2 - 1 = -3	-1 + (-3) = -4
10	-3 - (-2) = -1	-4 + (-1) = -5

Observation:

• The positions repeat in a cycle of 6 stages:

position sequence = 0, 1, -1, -4, -5, -3, 0, 1, -1, -4, -5, -3, ...

• So instead of computing all steps up to huge n, we can use mod 6.

---

Step 2: Map n mod 6 → position

Looking at the first 6 positions:

n % 6	position
0	0
1	1
2	-1
3	-4
4	-5
5	-3

✅ Perfect! This gives O(1) solution for very large n.

---

Step 3: C# Implementation

public static class Dancer
{
    public static int GetPositionAt(int n)
    {
        switch (n % 6)
        {
            case 0: return 0;
            case 1: return 1;
            case 2: return -1;
            case 3: return -4;
            case 4: return -5;
            case 5: return -3;
            default: return 0; // never happens
        }
    }
}

---

✅ Step 4: Test cases

Console.WriteLine(Dancer.GetPositionAt(3));        // -4
Console.WriteLine(Dancer.GetPositionAt(100000));   // -5
Console.WriteLine(Dancer.GetPositionAt(2147483647));// 1

• Works for huge n (up to 2,147,483,647)

• Uses constant memory

• O(1) CPU → very efficient

==============================================

private int GetStep(int n)

        {

            if (n == 0) return 0;

            if (n == 1) return 1;

             if (n == 2) return -2;

            int prev2 = 1;

            int prev1 = -2;

            int step = 0;

            for (int i = 3; i <= n; i++)

            {

                step = prev1 - prev2;

                prev2 = prev1;

                prev1 = step;

            }

            return step;

        }

        // Hàm tính position_n

        private int GetPosition(int n)

        {

            int pos = 0;

            for (int i = 0; i <= n; i++)

            {

                pos += GetStep(i);

            }

            return pos;

        }