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
import kotlin.math.abs
@Suppress("NAME_SHADOWING")
class Solution {
fun countOfPairs(n: Int, x: Int, y: Int): IntArray {
var x = x
var y = y
val answer = IntArray(n)
var distance = n - 1
var k = distance - 1
while (distance > 0) {
answer[k] = (n - distance) * 2
distance--
k--
}
if (x > y) {
val tmp = x
x = y
y = tmp
}
val skip = y - x
if (skip < 2) {
return answer
}
for (i in 1 until n) {
for (j in i + 1..n) {
val oldDistance = j - i
val newDistance = (abs((x - i)) + abs((y - j)) + 1)
if (newDistance < oldDistance) {
answer[oldDistance - 1] -= 2
answer[newDistance - 1] += 2
}
}
}
return answer
}
}