If you know the solution to it, Can you please tellme that how did you solved it so easily… it would be a great pleasure … thankyou.
I am also struggling on testcase 7. I get a result of 3972, while the outcome should be 3142894.
What I do is:
- Find the median
- Calculate from each house the distance Y from that median
- Take the smallest X and substract that from the largest X
- The sum of steps 2 and 3 results in 3972.
I saw another post that suggested similar logic and also warned for testcase 7, but unfortunately I could not find that post back. Does anyone have suggestions to help me further? Thank you
As several other have mentioned the solution is a lot simpler than you would imagine. DataType is important because some calculations go over 4 billion.
- The only optimization you need to calculate is where the main line goes on the Y axis.
- The main line always travels the length between the leftmost building to the rightmost building.
- Buildings always connect to the main line via straight segments or they are on the Main line.
The only calculation involving division or multiplication is when dividing total number of houses(n) by 2
so let, k = n/2
now k is a float
the best way is to round it to lower.
so use integer(n)
for median(m) = (arrayof_y_coords_sort_ascedning)[ int(n/2) ]