Hard
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 <= 105
1 <= x, y <= n
import kotlin.math.max
import kotlin.math.min
class Solution {
fun countOfPairs(n: Int, x: Int, y: Int): LongArray {
val result = LongArray(n)
val leftCount = (min(x, y) - 1)
val rightCount = (n - max(x, y))
val circleCount = n - leftCount - rightCount
circleInternal(circleCount, result)
lineToCircle(leftCount, circleCount, result)
lineToCircle(rightCount, circleCount, result)
lineToLine(leftCount, rightCount, if (x == y) 1 else 2, result)
lineInternal(leftCount, result)
lineInternal(rightCount, result)
return result
}
private fun lineToCircle(lineCount: Int, circleCount: Int, curRes: LongArray) {
val circleLen = circleCount / 2 + 1
var curModifier = 0
for (i in 1 until circleLen + lineCount) {
if (i <= min(lineCount, circleLen)) {
curModifier += 4
} else if (i > max(lineCount, circleLen)) {
curModifier -= 4
}
curRes[i - 1] += curModifier.toLong()
if (i <= lineCount) {
curRes[i - 1] = curRes[i - 1] - 2
}
if (i >= circleLen && circleCount % 2 == 0) {
curRes[i - 1] = curRes[i - 1] - 2
}
}
}
private fun lineToLine(lineCount1: Int, lineCount2: Int, initialDis: Int, curRes: LongArray) {
var curModifier = 0
for (i in 1 until lineCount1 + lineCount2) {
if (i <= min(lineCount1, lineCount2)) {
curModifier += 2
} else if (i > max(lineCount1, lineCount2)) {
curModifier -= 2
}
curRes[i - 1 + initialDis] += curModifier.toLong()
}
}
private fun lineInternal(lineCount: Int, curRes: LongArray) {
for (i in 1 until lineCount) {
curRes[i - 1] += (lineCount - i) * 2L
}
}
private fun circleInternal(circleCount: Int, curRes: LongArray) {
for (i in 0 until circleCount / 2) {
if (circleCount % 2 == 0 && i + 1 == circleCount / 2) {
curRes[i] += circleCount.toLong()
} else {
curRes[i] += circleCount * 2L
}
}
}
}