Math solution, O(n), 4ms
Spent quite a lot of time during contest to come up with maths for this one.\n# Intuition\n Describe your first thoughts on how to solve this problem. \nHouses 
Spent quite a lot of time during contest to come up with maths for this one.\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nHouses and their connections can be represented as a graph. Graph can be divided into different paths for which calculation becomes trivial.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet\'s make some definitions\n## Definitions\n- `line` looks like this:  \n![image.png](https://assets.leetcode.com/users/images/d178188f-d189-4374-b432-2267eb2518a2_1705837582.5628984.png)\n- `circle` looks like this:\n![image.png](https://assets.leetcode.com/users/images/915aaf90-c1c9-4009-a4ed-6f92938b162d_1705837703.3103843.png)\n- let\'s call such a figure `half`. We consider only green and blue part of it:\n![image.png](https://assets.leetcode.com/users/images/cde9248c-2f7b-4579-98c4-6a43b7bcfb4a_1705837981.3135223.png)\n- finally let\'s define `disjoin` this way. Note 2 vertices in the middle:\n![image.png](https://assets.leetcode.com/users/images/8d0153ee-dfa8-4e7e-b41e-c49742f102d3_1705838044.2395284.png)\n\n## Graph decomposition\nNow let\'s see how we can decompose our graph using these structures:\n\n- Suppose, initial graph is:\n![image.png](https://assets.leetcode.com/users/images/1f71ec8f-042b-4b44-9cd2-96b6e94f4144_1705838271.439508.png)\nWhich corresponds to the input: n=9, x=3, y=7\nWe\'re going to decompose this input of 1 `disjoint`, 1 `circle` and 4 `half`\'s\n\nHere are they:\n\n`disjoint`\n\n![image.png](https://assets.leetcode.com/users/images/c3ff6c42-eaf2-4e7d-9b7c-19fc403c5864_1705838425.1227236.png)\n\n`circle`\n![image.png](https://assets.leetcode.com/users/images/670f4273-4cad-435c-beeb-8e105374e733_1705838494.1531923.png)\n\n`half`\'s\n![image.png](https://assets.leetcode.com/users/images/3a07a259-b7e8-4511-b504-dfdaee2bddc9_1705838538.8392732.png)\n![image.png](https://assets.leetcode.com/users/images/176e1195-1b65-48c9-a37c-24defaf42f55_1705838600.4128954.png)\n![image.png](https://assets.leetcode.com/users/images/455e6de9-f29d-4678-a746-89868b5aa2cc_1705838695.5060706.png)\n![image.png](https://assets.leetcode.com/users/images/df4487d1-b2ef-45e5-a111-0295bd5f7272_1705838741.030639.png)\n\nAll the other types of graphs can be decomposed using the same figures as well.\nNow if we count the simple figures one-by-one and sum everything up we will come up with the answer.\n## Calculation\nThis part is a bit tricky for `half`and `disjoint`\n- `line` - simple, each distance `i` present `2 * (n - i - 1)` times\n- `circle` - again simple, just need to keep track if the number of nodes is even or odd\n- `half` - the idea is to calculate the pairs between the green and blue vertices and their distances.\n- `disjoint` - complex figure. We calculate left and right lines first and then doing the same as the `half`. See the code for it.\n\nIt can be seen, that this way we find the optimal path lengths from each house to every other.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code\n```\nclass Solution {\n  public long[] countOfPairs(int n, int x, int y) {\n    long[] res = new long[n];\n    if (x > y) {\n      int tmp = y;\n      y = x;\n      x = tmp;\n    }\n    int dist = y - x;\n    if (dist == 0 || dist == 1) {\n      line(res, n);\n      return res;\n    }\n    if (x != 1 && y != n) {\n      // disjoin\n      disjoin(res, x - 1, n - y);\n    } else if (x != 1 || y != n) {\n      // line\n      line(res, n - dist);\n    }\n    // circle\n    circle(res, dist + 1);\n    if (x != 1) {\n      half(res, x - 1, dist / 2);\n      half(res, x - 1, dist / 2 + dist % 2);\n    }\n    if (n != y) {\n      half(res, n - y, dist / 2);\n      half(res, n - y, dist / 2 + dist % 2);\n    }\n    return res;\n  }\n\n  private static void line(long[] arr, int n) {\n    for (int i = 0; i < n; i++) {\n      arr[i] += (n - i - 1) * 2;\n    }\n  }\n\n  private static void circle(long[] arr, int n) {\n    int finish = n / 2 - 1, add = 2 * n;\n    for (int i = 0; i < finish; i++) {\n      arr[i] += add;\n    }\n    if (n % 2 == 0) {\n      arr[finish] += n;\n    } else {\n      arr[finish] += add;\n    }\n  }\n\n  private static void half(long[] arr, int f, int s) {\n    int min, max, dist = f + s;\n    if (f < s) {\n      min = f;\n      max = s;\n    } else {\n      min = s;\n      max = f;\n    }\n    for (int i = 1; i < min; i++) {\n      arr[i] += 2 * i;\n    }\n    for (int i = min; i <= max; i++) {\n      arr[i] += 2 * min;\n    }\n    for (int i = max + 1; i < dist; i++) {\n      arr[i] += 2 * (dist - i);\n    }\n  }\n\n  private static void disjoin(long[] arr, int f, int s) {\n    // left line\n    line(arr, f + 1);\n    // right line\n    line(arr, s + 1);\n    // disjoin\n    int min, max, dist = f + s;\n    if (f < s) {\n      min = f;\n      max = s;\n    } else {\n      min = s;\n      max = f;\n    }\n    for (int i = 1; i < min; i++) {\n      arr[i + 1] += 2 * i;\n    }\n    for (int i = min; i <= max; i++) {\n      arr[i + 1] += 2 * min;\n    }\n    for (int i = max + 1; i < dist; i++) {\n      arr[i + 1] += 2 * (dist - i);\n    }\n  }\n}\n```
['Math', 'Java']