Short math O(n) solution in C++
This post is a clone of the solution for the hard verion 3017. Count the Number of Houses at a Certain Distance II.\n\n# Approach\nSolving this problem with mat
This post is a clone of the solution for the hard verion [3017. Count the Number of Houses at a Certain Distance II](https://leetcode.com/problems/count-the-number-of-houses-at-a-certain-distance-ii/solutions/4602644/short-math-o-n-solution-in-c/).\n\n# Approach\nSolving this problem with math includes counting in three cases:\n1. The house pairs in the cycle - every house can have two pairing other houses, up until the mirror house on the cycle, which is the mere house to pair with.\n1. The house pairs between the two tails - it forms a line, which is easy, but remember to exclude the pairs with the two houses on the cycle, if there are two.\n1. The house pairs between a tail and the cycle - the most tricky case - two distances matter - the distance between a tail house to the connecting house, and the distance between a cycle house to it. Such a two factor relationship forms a matrix, and cells on every diagonal line have the same house to house distance.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```cpp []\nvector<int> countOfPairs(int n, int x, int y) {\n    if (y < x) swap(x, y);\n\n    vector<int> ans(n);\n    int cycle = y - x + 1, halfCycle = cycle - 1 >> 1, tail1 = x - 1, tail2 = n - y;\n    int tailToTail = tail1 + tail2 + 1 + (x != y);\n\n    // in the cycle\n    for (int i = 0; i < halfCycle; i++)\n        ans[i] = cycle * 2;\n    if (cycle % 2 == 0)\n        ans[halfCycle] = cycle;\n\n    // tail to tail\n    for (int i = 1; i < tailToTail; i++)\n        ans[i - 1] += (tailToTail - i) * 2;\n    if (x != y) {\n        ans[0] -= 2;\n        for (int tail : {tail1, tail2})\n            for (int i = 1; i <= tail; i++)\n                ans[i] -= 2;\n    }\n\n    // tails to the cycle\n    for (int tail : {tail1, tail2}) {\n        for (int i = 1; i < tail + halfCycle; i++)\n            ans[i] += 4 * min({tail, halfCycle, i, tail + halfCycle - i});\n        if (cycle % 2 == 0)\n            for (int i = 1; i <= tail; i++)\n                ans[i + halfCycle] += 2;\n    }\n\n    return ans;\n}\n```
['Math', 'C++']