Minimum Robot Moves

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows: The first line of each test case contains a single integer ‘X’ denoting the final coordinate of the robot.

For test case 1 : We will print 3 because: If all three moves are taken to the right then the robot will end up at the position 1 + 2 + 3 = 6. For test case 2 : We will print 2 because: If the first two moves are taken to the right then the robot will end up at the position 1 + 2 = 3. Note that moving 1 unit to right, then 2 units to left and then 3 units to the right will also end up at position 3, but here the moves required are equal to three and a more optimal solution using two moves exists.

Brute Force

The primary observation for the question is that the answer will always exist.

Now, moving right for the first ‘N’ moves will result in reaching the coordinate (N * (N + 1) ) / 2, so we can easily conclude that at least ‘N’ moves are needed such that the value of (N * (N + 1) ) / 2 is greater than or equal to ‘X’. Now if the sum of the first N numbers is equal to ‘X’ then we can say that moving to the right in all the N moves will result in reaching the desired ‘X’ coordinate.

What if the value of (N * (N + 1) ) / 2 exceeds ‘X’? This is the case when a few of the moves in between should be taken to the left! If the robot moves to the left in one of the moves, then this results in decreasing the position of the old coordinate by twice the move number, this is because earlier that particular move contributed to increasing the coordinate value by the corresponding move number, but now it contributes in decreasing the coordinate value. From this observation, we can conclude that if the difference between (N * (N + 1) ) / 2 and ‘X’ is divisible by two (both the values have the same parity), then we can reach ‘X’ by moving the step number ( (N * (N + 1) ) / 2 - X ) / 2 to the left instead of the right. If the difference is not divisible by two (summation of first N numbers has different parity than X) then check for the next N until you find the N with parity of ‘X’ and summation of first N numbers equal to each other.

The steps are as follows :

Initialize ‘moves’ equal to 0, this will store the minimum moves required to reach the final position.
Run a while loop, for each iteration, check if the value of moves * (moves + 1) / 2 is greater than equal to ‘X’ and has the same parity as ‘X’, return the value of ‘moves’ if both the conditions hold true, else increment the value of ‘moves’ to check for the next value.

Time Complexity

O( sqrt ( X ) ), where X denotes coordinate on the x-axis

We find a value of ‘N’ such that the summation of first ‘N’ natural numbers is greater than ‘X’, we check this iteratively and it comes out to be of the order sqrt(X) as a summation of first N numbers is equal to N*(N + 1)/2.

Hence the time complexity is O( sqrt(X) ).

Space Complexity

O( 1 )

No extra space is used.

Hence the space complexity is O( 1 ).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation For Sample Input 1 :

Sample Input 2 :

Sample Output 2 :