Simple Explanation✅ for beginners | C++✅ | Math
Approach

Convert and Order the Special Houses:
Since houses are numbered from 1 to n and the extra edge connects house x to house y, we first convert these to

## Approach

1. **Convert and Order the Special Houses:**  
   Since houses are numbered from 1 to *n* and the extra edge connects house *x* to house *y*, we first convert these to 0‑indexed numbers and make sure that *x* ≤ *y*. (If not, we swap them.) This standardization simplifies the formulas later.

2. **Observing the Graph Structure:**  
   The city’s street network is basically a chain (1–2–…–*n*) plus one extra “bridge” (an extra edge) connecting house *x* and house *y*. Thus, for any two houses (say with indices *i* and *j*, where *i* < *j*), the distance between them is:
   - The **chain distance**: simply *j – i* (walking along the main road), or 
   - The **shortcut distance**: a route that goes from *i* to *x*, then takes the extra edge (cost = 1), then goes from *y* to *j*. (More generally, it is computed as “distance from *i* to *x* plus 1 plus distance from *y* to *j*”.)
   
   The actual distance is the minimum of these two values.

3. **Counting Pairs by Their Distance:**  
   Our goal is to count, for each possible distance *k* (from 1 to *n*), how many **ordered** pairs (house1, house2) have that minimum distance. (Note that since (a, b) and (b, a) are both counted, we finally multiply by 2.)  
   
   A naive solution would loop over all pairs in O(*n*²) time, but that is too slow when *n* is large.

4. **Using a Difference Array for Efficient Range Updates:**  
   The key observation is that the contributions to each distance come from many pairs that often form a contiguous range. (In other words, many pairs share the same distance or the distances change in a predictable “range‐update” pattern.)  
   
   Therefore, we use a difference array called `result` to “mark” contributions over contiguous ranges. For example, if a whole block of pairs contributes 1 to every distance in the range [L, R–1], we can do:
   ```cpp
   result[L]++;    // start adding 1 from L onward
   result[R]--;    // stop adding 1 from R onward
   ```
   Later, a prefix sum over the difference array recovers the actual counts per distance.

5. **Breaking the Problem into Cases:**  
   The code distinguishes two cases:
   - **Case 1: When the extra edge is a self‐loop (i.e. *x* == *y*).**  
     In that case the “shortcut” does nothing, and the answer is exactly the counts coming from the chain.
   - **Case 2: When *x* ≠ *y*.**  
     In this case the extra edge offers an alternative (often shorter) path. The code splits the pairs into several groups according to where the starting house lies (for instance, houses before *x*, houses between *x* and *y*, houses after *y*) and then uses several loops with range updates to add the contribution of each group. (The formulas in these updates are based on the two possible routes and the “overlap” between them.)

6. **Finalizing the Answer:**  
   After all the updates are done into the `result` difference array, a prefix sum “sweeps” through to produce the actual counts for distances 1 through *n*. Finally, since the pairs are considered in both orders, every count is multiplied by 2.

---

## Code explained with comments


```cpp
#define ll long long
class Solution {
public:
    vector<long long> countOfPairs(int n, int x, int y) {
        // Create a difference array "result" with n+1 elements (all 0).
        // We use a difference array so that we can efficiently update
        // counts for a contiguous range of distances.
        vector<ll> result(n+1, 0);
        
        // Convert x and y from 1-indexed to 0-indexed.
        x--; y--;
        
        // Ensure x is less than or equal to y. This standardizes our formulas.
        if(x > y){
            // Swap x and y without using a temporary variable.
            x = x ^ y;
            y = x ^ y;
            x = x ^ y;
        }
        
        // --------------------
        // Case 1: x == y
        // --------------------
        // When x and y are the same, the extra street is essentially a self-loop.
        // So the graph is just a simple chain (1 to n) and every pair’s distance
        // is simply the difference along the chain.
        if(x == y){
            for (int i = 0; i < n - 1; i++){
                // For every valid pair distance from 1 to n-1,
                // we add 1 to the starting index (distance = 1) and subtract 1 past the end
                // of the range where this contribution holds.
                result[1]++;       // start adding from distance 1
                result[n-i]--;     // stop adding at distance (n - i)
            }
        }
        
        // --------------------
        // Case 2: x != y
        // --------------------
        // When x and y are different, the extra street creates a shortcut.
        // For every pair (i, j), the distance is the minimum between:
        //   - The chain distance: j - i, and
        //   - The shortcut distance: (distance from i to x) + 1 + (distance from y to j)
        // We will add contributions from different segments of houses.
        if(x != y){
            // Process houses with indices 0 to x (houses before or at x).
            for (int i = 0; i <= x; i++){
                // For a fixed house i (with i in [0, x]),
                // consider pairs that “jump” from near i to houses from y till the end.
                // The distance using the shortcut becomes: (x - i) + 1 + (j - y)
                // so that the range of possible distances is from (x - i + 1)
                // to (x - i + 1 + (n - y - 1)) = (x + n - i - y).
                result[x-i+1]++;              // add 1 starting at distance = x - i + 1
                result[x+n-i-y+1]--;           // subtract 1 after the last distance in this range
                
                // Also, consider pairs where the second house is between i+1 and x.
                // For these pairs the only path is along the chain.
                if (i < x) {
                    result[1]++;              // chain distance always starts at 1
                    result[x-i+1]--;          // stop at distance = x - i
                }
            }
            
            // Process houses from y to n-1 (houses at or after y).
            // These houses only have the chain path available (or contribute their chain distances).
            for (int i = y; i < n - 1; i++){
                result[1]++;                  // add contribution starting at distance 1
                result[n-i]--;                // subtract after distance = n - i
            }
            
            // Process houses that lie strictly between x and y.
            // For these houses (i from x+1 to y-1) the situation is more complicated,
            // since the alternative route might be taken in several different ways.
            for (int i = x + 1; i < y; i++){
                // --- First part: pairs from house i with houses before x ---
                // The extra distance added in the shortcut depends on the relative
                // position of i with respect to x and y.
                int fixed = min(i - x, 1 + y - i);
                result[fixed]++;              // update range starting at "fixed" distance
                result[fixed + x + 1]--;        // end the range after "fixed + x" distance
                
                // --- Second part: pairs from house i with houses after y ---
                fixed = min(y - i, 1 + i - x);
                result[fixed]++;              // update range starting at "fixed" distance
                result[fixed + n - y]--;         // end the range appropriately
                
                // --- Third part: pairs where the second house is also between i+1 and y-1 ---
                // Depending on the positions, we sometimes have two segments:
                int j = i + ((y - x) / 2) + 1;
                if(j < y){
                    // For the range where the chain (without shortcut) gives the distance:
                    result[1]++;          // start at distance 1
                    result[j - i]--;      // end at distance (j - i)
                    
                    // For the range where the shortcut is used, adjust the start and end.
                    result[1 + i - x + 1]++;      
                    result[1 + i - x + 1 + y - j]--;
                }
                else{
                    // Otherwise, update using only the chain distance.
                    result[1]++;
                    result[y - i]--;
                }
            }
        }
        
        // --------------------
        // Finalizing the result:
        // --------------------
        // The difference array "result" now has updates in the form:
        //   result[L]++ and result[R]-- for many ranges.
        // We now convert it to the actual counts for each distance via prefix sums.
        result[0] = 0; // ensure index 0 is set correctly
        for (int i = 1; i <= n; i++) {
            result[i] += result[i - 1];
        }
        
        // Build the final answer array (distances 1 to n) from our result.
        // (result[0] corresponds to distance 0 which we do not need.)
        vector<ll> ans(result.begin() + 1, result.end());
        
        // Multiply by 2 since every pair is counted in both orders (i.e. (a, b) and (b, a)).
        for (auto &j : ans) {
            j *= 2;
        }
        return ans;
    }
};
```

---


# Complexity
- Time complexity: O(N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

['Math', 'Prefix Sum', 'C++']