Last Updated: 22 Oct, 2021
Minimum Robot Moves
Easy
Asked in companies
A robot can move along the x-axis, it starts from the origin and wants to reach the ‘X’ coordinate. Find the number of moves it requires to complete the task.
In each move, it has to exactly move some units to the left/right of its current position. The number of units it moves in a move is equal to the move number. That is: it moves exactly one unit in move - 1, exactly two units in move - 2 and exactly ten units in move - 10. Find the minimum number of moves required to reach the ‘X’ coordinate. Print ‘-1’ if it is not possible to reach the location.
For Example :
If X = 6
If all three moves are taken to the right then the robot will end up at 1 + 2 + 3 = 6, so a minimum of three moves are needed.
Input Format :
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.
Output Format :
For each test case, print the number of moves required to reach the final position.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
1 ≤ X ≤ 10^9
Time limit: 1 sec
Approaches
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.