Medium
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.
Example 1:
Input: n = 3, x = 1, y = 3
Output: [6,0,0]
Explanation: Let’s look at each pair of houses:
Example 2:
Input: n = 5, x = 2, y = 4
Output: [10,8,2,0,0]
Explanation: For each distance k the pairs are:
Example 3:
Input: n = 4, x = 1, y = 1
Output: [6,4,2,0]
Explanation: For each distance k the pairs are:
Constraints:
2 <= n <= 100
1 <= x, y <= n
public class Solution {
public int[] countOfPairs(int n, int x, int y) {
int[] answer = new int[n];
int distance = n - 1;
int k = distance - 1;
while (distance > 0) {
answer[k] = (n - distance) * 2;
distance--;
k--;
}
if (x > y) {
int tmp = x;
x = y;
y = tmp;
}
int skip = y - x;
if (skip < 2) {
return answer;
}
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
int oldDistance = j - i;
int newDistance = Math.abs(x - i) + Math.abs(y - j) + 1;
if (newDistance < oldDistance) {
answer[oldDistance - 1] -= 2;
answer[newDistance - 1] += 2;
}
}
}
return answer;
}
}