Count the Number of Houses at a Certain Distance I - Problem

You are given three positive integers n, x, and y. In a city, there exist houses numbered 1 to n connected by n streets.

There is a street connecting the house numbered i with the house numbered i + 1 for all 1 <= i <= n - 1. An additional street connects the house numbered x with the house numbered y.

For each k, such that 1 <= k <= n, you need to find the number of pairs of houses (house1, house2) such that the minimum number of streets that need to be traveled to reach house2 from house1 is k.

Return a 1-indexed array result of length n where result[k] represents the total number of pairs of houses such that the minimum streets required to reach one house from the other is k.

Note that x and y can be equal.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, x = 1, y = 3

› Output: [3,0,0]

💡 Note: Houses 1-3 with shortcut 1-3. Pairs: (1,2) distance = min(1, 2, 4) = 1; (1,3) distance = min(2, 1, 4) = 1; (2,3) distance = min(1, 2, 3) = 1. All 3 pairs have distance 1.

Example 2 — No Shortcut Effect

$ Input: n = 4, x = 1, y = 1

› Output: [3,2,1]

💡 Note: Since x = y, no actual shortcut exists. Pairs: (1,2), (2,3), (3,4) have distance 1 (3 pairs). Pairs (1,3), (2,4) have distance 2 (2 pairs). Pair (1,4) has distance 3 (1 pair).

Example 3 — Shortcut Creates Shorter Paths

$ Input: n = 5, x = 2, y = 4

› Output: [4,4,2,0,0]

💡 Note: With shortcut 2-4, some longer distances become shorter. For example, distance from house 1 to house 5 can be 4 (direct) or 3 (via shortcut: 1→2→4→5).

Constraints

3 ≤ n ≤ 100
1 ≤ x, y ≤ n

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is that the shortcut between houses x and y creates alternative paths that may be shorter than the direct linear path. We need to calculate the minimum distance between every pair of houses considering both the direct path and paths using the shortcut. Best approach is the optimized distance calculation with Time: O(n²), Space: O(n).

Common Approaches

✓ Brute Force BFS for Every Pair

⏱️ Time: O(n³) Space: O(n²)

For each house, use BFS to calculate shortest distance to every other house. Then count pairs by distance.

Optimized Distance Calculation

⏱️ Time: O(n²) Space: O(n)

Instead of running BFS from every house, calculate shortest distance between any two houses using mathematical formulas considering the shortcut.

Brute Force BFS for Every Pair — Algorithm Steps

For each house i from 1 to n
Run BFS to find shortest distance from i to all other houses
Count pairs by their distances

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list with linear streets and shortcut

BFS from Each House

Run BFS from every house to find shortest distances

Count Pairs

Count house pairs by their shortest distance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 105

int graph[MAX_N][MAX_N];
int graph_size[MAX_N];
int dist[MAX_N];
int queue[MAX_N * MAX_N];
int front, rear;

void add_edge(int u, int v) {
    graph[u][graph_size[u]++] = v;
}

void bfs(int start, int n) {
    for (int i = 0; i <= n; i++) dist[i] = -1;
    dist[start] = 0;
    front = rear = 0;
    queue[rear++] = start;
    
    while (front < rear) {
        int curr = queue[front++];
        for (int i = 0; i < graph_size[curr]; i++) {
            int neighbor = graph[curr][i];
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[curr] + 1;
                queue[rear++] = neighbor;
            }
        }
    }
}

int* solution(int n, int x, int y) {
    // Initialize graph
    memset(graph_size, 0, sizeof(graph_size));
    
    // Linear connections
    for (int i = 1; i < n; i++) {
        add_edge(i, i + 1);
        add_edge(i + 1, i);
    }
    
    // Additional connection x-y
    if (x != y) {
        add_edge(x, y);
        add_edge(y, x);
    }
    
    int* result = (int*)calloc(n, sizeof(int));
    
    // For each house, run BFS to find distances to all others
    for (int start = 1; start <= n; start++) {
        bfs(start, n);
        
        // Count distances from this start house
        for (int end = start + 1; end <= n; end++) {
            if (dist[end] > 0) {
                result[dist[end] - 1]++;
            }
        }
    }
    
    return result;
}

int main() {
    int n, x, y;
    scanf("%d", &n);
    scanf("%d", &x);
    scanf("%d", &y);
    
    int* result = solution(n, x, y);
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

BFS from each of n houses takes O(n²) time, total n × n² = O(n³)

⚠ Quadratic Growth

Space Complexity

O(n²)

Need to store distance matrix for all pairs of houses

⚠ Quadratic Space

8.8K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Count the Number of Houses at a Certain Distance I - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force BFS for Every Pair — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler