PROBLEM LINK
ALUN2021-LAMA
DIFFICULTY
Easy-medium
PREREQUISITES
Maths
EXPLANATION
Lets assume A1, A2 and A3 be located at points (0,A1), (1,A2) and (2,A3) respectively on a cartesian coordinate. If A1, A2 and A3 have to form an AP (arithmetic-progression) they must lie on a single straight line because if X-coordinates are in AP then Y -coordinates are also in AP on a straight line(property).
It is also given that we can only increase(not decrease) the Y-coordinates. Let’s fix the point A1 then two cases arise as follows:
- Case 1: A2>A3
This straight line has optimal solution because if we rotate it about A1 anticlockwise it will cost us more to bring all the points on the same line.
Then the question is reduced to - how much units is needed to bring A3 on the line , and solution is given by-
(2*A2 - A1) - A3
- Case 2: A3>=A2
This line can bring optimal solution if (A1+A3)%2=0 because all three points must have integral coordinates and A2 = (A1+A3)/2.
If (A1+A3)%2 != 0 then increase A3 by one and redraw the graph. Then the problem is reduced to - how many units is needed to bring A2 on the same line and its solution is given by -
((A1 + A3) / 2) - A2
Note: - If (A1+A3)%2=1 final answer is one more than the above expression because we used one unit to increase A3
TIME COMPLEXITY
Simple if else conditions, therefore:
O(1)
SOLUTION
Here is my whole solution code.