 # SIGNMOVE Editorial

Tester: Aryan, Takuki Kurokawa
Editorialist: Pratiyush Mishra

Simple

None

# PROBLEM:

Initially, Chef is at coordinate 0 on X-axis. For each i=1,2,…,N in order, Chef does the following operation:

• If Chef is at a non-negative coordinate, he moves i steps backward (i.e, his position’s coordinate decreases by i), otherwise he moves i steps forward (i.e, his position’s coordinate increases by i).

You are given the integer N. Find the final position of Chef on the X-axis after N operations.

# EXPLANATION:

Note the following:

1. Chef always starts at the origin.
2. i always begins at 1.
3. Chef’s action depends on the previous state and i.

The above statements are enough to prove that chef’s position is a function of i alone, i.e it can be written as position = p(i).

p(0) = 0
p(1) = -1
p(2) = 1
p(3) = -2
p(4) = 2
p(5) = -3
p(6) = 3
and so on …

Note that:
At even i's, p(i) = \frac{i}{2}
At odd i's, p(i) = \frac{-(i+1)}{2}

Thus, Chef’s position at N = p(N).

p(N) = \begin{cases} \frac{N}{2} \;\;\;\;if \; N\; is\; even \\ \frac{-(N+1)}{2} \;\;\;\;if \; N\; is\; odd \end{cases}

# TIME COMPLEXITY:

The above calculation can be done in constant time. Hence, the solution has a time complexity of O(1).

1 Like