C++ (59ms Beats 100%) | Detailed Explanation | 3 Cases
Intuition\nAll houses are connected in a line except two houses and any graph algorithm would not work for the given constraints. So, there must be a logical wa
# Intuition\nAll houses are connected in a line except two houses and any graph algorithm would not work for the given constraints. So, there must be a logical way to solve the problem.\n\n# Approach\nIf x==y or x and y differ by 1 (Base Case) i.e. no new path is added, we can directly write the answer. The answer will be\n[2*(n-1),2*(n-2),...,4,2,0]\nWe can divide the problem into subproblems as follows:\n\nPart I (Shortest Path) : Take the extra street added and remove the houses between them. Now there is only one straight path.\nNow, we know the answer for the base case.The length of the path be m.\n\nPart II (Loop) : Let loop length be \'l\' and path length be \'p\'.\nNow for p=1, we have 2*l paths but we already took two of them before (the path from x to y and y to x). \npaths(1) = 2*(l-1)\nFor all other paths paths(p) = 2*l.\nBut wait, till what value of p, we need to go.\np will range from 1 to l/2.Why??\nIf p is greater than l/2 then there is another shorter path which will be taken.\n\nBut is everything fine?Did we missed something. Oh no!!\nThere is some problem we need to check.\nIf l is odd : No problem.Everything is fine.\nIf l is even : There are 2 ways to go from one house to another at a distance l/2 and since we are counting each path twice we need to take only l paths. So paths(l/2) = l.\n\nPart III (Outside Loop and Inside Loop Connections) :\nThere will be paths connecting left and loop and paths connecting loop and right.\nThe length of left will be from 1 to x. \nHere in the image from 3_4, 2_4 and 1_4.\nPaths of a given length inside loop will be 2. This length will be same as in part II. If length will be from 1 to l/2.\nBut here also we previously added the one length path between x and y.\nSo, we have only one path of length 1.\nIf l is even, then the number of paths of length l/2 will be 1 as there are 2 ways to reach the same house.\nWe can write seaprately for path length 1 and path length l/2(for even l) for all left and right.\nTotal time for both left and right. $$O(left+right)$$\nNow, for paths of length 2 to l/2 and paths on left from 1 to left.\nSimilarly for right.\nThis will take a time of $$O((l/2)*(left+right))$$. \nThis will not work we need to optimize.\nNow if you count how many paths we will get for a particular length, there is a pattern.\nif you see this carefully it is just like dice.\nYou can take values for left on one axis and loop on another axis and form a grid. Similarly for right and loop as well.\nSee, the example here :\nO **2 3 4 5 6**\n**1**  3 4 5 6 7\n**2**  4 5 6 7 8\n**3**  5 6 7 8 9\n**4**  6 7 8 9 10\nThe path starts from length 3 (we already took length 2 path). The count of path increases from 1 to min(X-axis length,Y-axis length) and decrease again.\nNow,time complexity to calculate this part reduces to $$O(l+left+right)$$ which is approximately $$O(n)$$. \n![Houses.png](https://assets.leetcode.com/users/images/4f802cd3-8bf2-4355-be71-b78689b29411_1705826335.4464614.png)\n\n\n# Complexity\n- Time complexity:\n$$O(n)$$ : Time required to store the result as well as to calculate all 3 parts.\n\n- Space complexity:\n$$O(n)$$ : Used for storing the result.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<long long> countOfPairs(int n, int x, int y) \n    {\n        if(x>y) swap(x,y);\n        vector<long long> v(n,0);\n        int left=x-1,right=n-y;\n\n        //Base Case\n        if(x==y || abs(x-y)==1)\n        {\n            for(int i=n-2;i>=0;i--)\n                v[i] = v[i+1]+2; \n        }\n        else\n        {\n            //m = length of path without houses inside loop\n            //loop = length of the loop\n            //Part I\n            int m=n+1-(y-x),loop=y-x+1;\n            for(int i=m-2;i>=0;i--)\n                v[i] = v[i+1]+2;\n\n            //If l is odd\n            if(loop&1)\n            {\n                //Part II\n                v[0]+=(loop-1)*2;\n                for(int i=1;i<loop/2;i++)\n                    v[i] += loop*2;\n                \n                //Part III\n                for(int i=0;i<left;i++)\n                    v[i+1]+=2;\n                int mini=min(loop/2-1,left),maxi=loop/2+left;\n                for(int i=2;i<maxi;i++)\n                    v[i] += 4*min(min(i-1,maxi-i),mini);\n                \n                for(int i=0;i<right;i++)\n                    v[i+1]+=2;\n                mini=min(loop/2-1,right),maxi=loop/2+right;\n                for(int i=2;i<maxi;i++)\n                    v[i] += 4*min(min(i-1,maxi-i),mini);\n            }\n            //If l is even\n            else\n            {\n                //Part II\n                v[0]+=(loop-1)*2;\n                for(int i=1;i<loop/2-1;i++)\n                    v[i] += loop*2;\n                v[loop/2-1] += loop;\n\n                //Part III\n                for(int i=0;i<left;i++)\n                {\n                    v[i+1]+=2;\n                    v[i+loop/2]+=2;\n                }\n                int mini=min(loop/2-2,left),maxi=loop/2+left-1;\n                for(int i=2;i<maxi;i++)\n                    v[i] += 4*min(min(i-1,maxi-i),mini);\n                \n                for(int i=0;i<right;i++)\n                {\n                    v[i+1]+=2;\n                    v[i+loop/2]+=2;\n                }\n                mini=min(loop/2-2,right),maxi=loop/2+right-1;\n                for(int i=2;i<maxi;i++)\n                    v[i] += 4*min(min(i-1,maxi-i),mini);\n            }\n        }\n        return v;\n    }\n};\n```
['Array', 'Math', 'Counting', 'C++']