C- Implementation ::: How does the solution work Mathematically


#1

Lets Say we have two points X=(a,b), Y=(c,d)

Assuming point X is closer to the origin, the matrix might look something like below
|..............X...............................................................|
|..............................................................................|
|..............................................................................|



|................................................Y.............................|

Let us assume
[1] (c-a)<(d-b)-------------------------------------(1)
From X, we shall move diagonally right-down till we reach the row in which point Y is present.
This action will take (c-a) steps exactly and we would be in the Cth row of the matrix.-------(2)

Our current position will thus be (c,b+c-a)

To reach to our destination(c,d) from point (c,b+c-a) we will need exactly (d-(b+c-a)) number of steps------(3)

from (2) and (3),
Total steps we took are = (c-a) + (d-b-c+a)=d-b

[2] Similarly it can be proven when
(c-a)>(d-b) then the min number of steps required are (c-a)

Hence it is always true that to reach from X to Y,
min steps= Max(|d-b|,|c-a|)

Code implementation:

int coverPoints(int* A, int n1, int* B, int n2) {
    int x1,y1,x2,y2,i,dist,X,Y;
    x1=A[0]; y1=B[0];
    for(i=1;i<n1;i++){
        x2=A[i],y2=B[i];
        X=(x1-x2)>0?(x1-x2):(x2-x1);
        Y=(y1-y2)>0?(y1-y2):(y2-y1);

        dist+=(X>Y?X:Y);
        x1=A[i];
        y1=B[i];
    }

    return dist;
}