3015. Count the Number of Houses at a Certain Distance I LeetCode Solution
In this guide, you will get 3015. Count the Number of Houses at a Certain Distance I LeetCode Solution with the best time and space complexity. The solution to Count the Number of Houses at a Certain Distance I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Count the Number of Houses at a Certain Distance I solution in C++
- Count the Number of Houses at a Certain Distance I solution in Java
- Count the Number of Houses at a Certain Distance I solution in Python
- Additional Resources
Problem Statement of Count the Number of Houses at a Certain Distance I
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:
– For the pair (1, 2), we can go from house 1 to house 2 directly.
– For the pair (2, 1), we can go from house 2 to house 1 directly.
– For the pair (1, 3), we can go from house 1 to house 3 directly.
– For the pair (3, 1), we can go from house 3 to house 1 directly.
– For the pair (2, 3), we can go from house 2 to house 3 directly.
– For the pair (3, 2), we can go from house 3 to house 2 directly.
Example 2:
Input: n = 5, x = 2, y = 4
Output: [10,8,2,0,0]
Explanation: For each distance k the pairs are:
– For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), and (5, 4).
– For k == 2, the pairs are (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), and (5, 3).
– For k == 3, the pairs are (1, 5), and (5, 1).
– For k == 4 and k == 5, there are no pairs.
Example 3:
Input: n = 4, x = 1, y = 1
Output: [6,4,2,0]
Explanation: For each distance k the pairs are:
– For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), and (4, 3).
– For k == 2, the pairs are (1, 3), (3, 1), (2, 4), and (4, 2).
– For k == 3, the pairs are (1, 4), and (4, 1).
– For k == 4, there are no pairs.
Constraints:
2 <= n <= 100
1 <= x, y <= n
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
3015. Count the Number of Houses at a Certain Distance I LeetCode Solution in C++
class Solution {
public:
vector<int> countOfPairs(int n, int x, int y) {
if (x > y)
swap(x, y);
const int ringLen = y - x + 1;
const int leftLineLen = x - 1;
const int rightLineLen = n - y;
vector<int> ans(n);
ans = addVectors(ans, bothInRing(n, ringLen));
ans = addVectors(ans, bothInTheSameLine(n, leftLineLen));
ans = addVectors(ans, bothInTheSameLine(n, rightLineLen));
ans = addVectors(ans, lineToRing(n, leftLineLen, ringLen));
ans = addVectors(ans, lineToRing(n, rightLineLen, ringLen));
ans = addVectors(ans, lineToLine(n, x, y, leftLineLen, rightLineLen));
for (int& freq : ans)
freq *= 2;
return ans;
}
private:
// Returns the contribution from the scenario where two houses are located in
// the ring.
vector<int> bothInRing(int n, int ringLen) {
vector<int> res(n);
for (int k = 1; k <= (ringLen - 1) / 2; ++k)
res[k - 1] += ringLen;
if (ringLen % 2 == 0)
res[ringLen / 2 - 1] += ringLen / 2;
return res;
}
// Returns the contribution from the scenario where two houses are either
// located in the left line [1, x) or the right line (y, n].
vector<int> bothInTheSameLine(int n, int lineLen) {
vector<int> res(n);
for (int k = 1; k <= lineLen; ++k)
res[k - 1] += lineLen - k;
return res;
}
// Returns the contribution from the scenario where one house is either
// located in the left line [1, x) or the right line (y, n] and the other
// house is located in the cycle.
vector<int> lineToRing(int n, int lineLen, int ringLen) {
vector<int> res(n);
for (int k = 1; k <= lineLen + ringLen; ++k) {
// min(
// at most k - 1 since we need to give 1 to the line,
// at most ringLen / 2 since for length > ringLen / 2, it can always be
// calculated as ringLen - ringLen / 2
// )
const int maxInRingLen = min(k - 1, ringLen / 2);
// max(at least 0, at lest k - lineLen)
const int minInRingLen = max(0, k - lineLen);
if (minInRingLen <= maxInRingLen) {
// Each ring length contributes 2 to the count due to the split of
// paths when entering the ring: One path traverses the upper half of
// the ring, and the other traverses the lower half.
// This is illustrated as follows:
// Path 1: ... -- x -- (upper half of the ring)
// Path 2: ... -- x -- (lower half of the ring)
res[k - 1] += (maxInRingLen - minInRingLen + 1) * 2;
if (minInRingLen == 0)
// Subtract 1 since there's no split.
res[k - 1] -= 1;
if (maxInRingLen * 2 == ringLen)
// Subtract 1 since the following case only contribute one:
// ... -- x -- (upper half of the ring) -- middle point
// ... -- x -- (upper half of the ring) -- middle point
res[k - 1] -= 1;
}
}
return res;
}
// Returns the contribution from the scenario where one house is in the left
// line [1, x) and the other house is in the right line (y, n].
vector<int> lineToLine(int n, int x, int y, int leftLineLen,
int rightLineLen) {
vector<int> res(n);
for (int k = 1; k <= leftLineLen + rightLineLen + 2; ++k) {
// min(
// at most leftLineLen,
// at most k - 1 - (x < y) since we need to give 1 to the right line
// and if x < y we need to give another 1 to "x - y".
// )
const int maxInLeft = min(leftLineLen, k - 1 - (x < y));
// max(at least 1, at least k - rightLineLen - (x < y))
const int minInLeft = max(1, k - rightLineLen - (x < y));
if (minInLeft <= maxInLeft)
res[k - 1] += maxInLeft - minInLeft + 1;
}
return res;
}
vector<int> addVectors(const vector<int>& a, const vector<int>& b) {
vector<int> res(a.size());
transform(a.begin(), a.end(), b.begin(), res.begin(), plus<int>());
return res;
};
};
/* code provided by PROGIEZ */3015. Count the Number of Houses at a Certain Distance I LeetCode Solution in Java
class Solution {
public int[] countOfPairs(int n, int x, int y) {
if (x > y) {
final int temp = x;
x = y;
y = temp;
}
final int ringLen = y - x + 1;
final int leftLineLen = x - 1;
final int rightLineLen = n - y;
int[] ans = new int[n];
ans = addVectors(ans, bothInRing(n, ringLen));
ans = addVectors(ans, bothInTheSameLine(n, leftLineLen));
ans = addVectors(ans, bothInTheSameLine(n, rightLineLen));
ans = addVectors(ans, lineToRing(n, leftLineLen, ringLen));
ans = addVectors(ans, lineToRing(n, rightLineLen, ringLen));
ans = addVectors(ans, lineToLine(n, x, y, leftLineLen, rightLineLen));
for (int i = 0; i < ans.length; ++i)
ans[i] *= 2;
return ans;
}
// Returns the contribution from the scenario where two houses are located in
// the ring.
private int[] bothInRing(int n, int ringLen) {
int[] res = new int[n];
for (int k = 1; k <= (ringLen - 1) / 2; ++k)
res[k - 1] += ringLen;
if (ringLen % 2 == 0)
res[ringLen / 2 - 1] += ringLen / 2;
return res;
}
// Returns the contribution from the scenario where two houses are either
// located in the left line [1, x) or the right line (y, n].
private int[] bothInTheSameLine(int n, int lineLen) {
int[] res = new int[n];
for (int k = 1; k <= lineLen; ++k)
res[k - 1] += lineLen - k;
return res;
}
// Returns the contribution from the scenario where one house is either
// located in the left line [1, x) or the right line (y, n] and the other
// house is located in the cycle.
private int[] lineToRing(int n, int lineLen, int ringLen) {
int[] res = new int[n];
for (int k = 1; k <= lineLen + ringLen; ++k) {
// min(
// at most k - 1 since we need to give 1 to the line,
// at most ringLen / 2 since for length > ringLen / 2, it can always be
// calculated as ringLen - ringLen / 2
// )
final int maxInRingLen = Math.min(k - 1, ringLen / 2);
// max(at least 0, at lest k - lineLen)
final int minInRingLen = Math.max(0, k - lineLen);
if (minInRingLen <= maxInRingLen) {
// Each ring length contributes 2 to the count due to the split of
// paths when entering the ring: One path traverses the upper half of
// the ring, and the other traverses the lower half.
// This is illustrated as follows:
// Path 1: ... -- x -- (upper half of the ring)
// Path 2: ... -- x -- (lower half of the ring)
res[k - 1] += (maxInRingLen - minInRingLen + 1) * 2;
if (minInRingLen == 0)
// Subtract 1 since there's no split.
res[k - 1] -= 1;
if (maxInRingLen * 2 == ringLen)
// Subtract 1 since the following case only contribute one:
// ... -- x -- (upper half of the ring) -- middle point
// ... -- x -- (upper half of the ring) -- middle point
res[k - 1] -= 1;
}
}
return res;
}
// Returns the contribution from the scenario where one house is in the left
// line [1, x) and the other house is in the right line (y, n].
private int[] lineToLine(int n, int x, int y, int leftLineLen, int rightLineLen) {
int[] res = new int[n];
for (int k = 1; k <= leftLineLen + rightLineLen + 2; ++k) {
// min(
// at most leftLineLen,
// at most k - 1 - (x < y) since we need to give 1 to the right line
// and if x < y we need to give another 1 to "x - y".
// )
final int maxInLeft = Math.min(leftLineLen, k - 1 - (x < y ? 1 : 0));
// max(at least 1, at least k - rightLineLen - (x < y))
final int minInLeft = Math.max(1, k - rightLineLen - (x < y ? 1 : 0));
if (minInLeft <= maxInLeft)
res[k - 1] += maxInLeft - minInLeft + 1;
}
return res;
}
private int[] addVectors(int[] a, int[] b) {
for (int i = 0; i < a.length; ++i)
a[i] += b[i];
return a;
}
}
// code provided by PROGIEZ3015. Count the Number of Houses at a Certain Distance I LeetCode Solution in Python
class Solution:
def countOfPairs(self, n: int, x: int, y: int) -> list[int]:
if x > y:
x, y = y, x
def bothInRing(ringLen: int) -> list[int]:
"""
Returns the contribution from the scenario where two houses are located
in the ring.
"""
res = [0] * n
for k in range(1, (ringLen - 1) // 2 + 1):
res[k - 1] += ringLen
if ringLen % 2 == 0:
res[ringLen // 2 - 1] += ringLen // 2
return res
def bothInTheSameLine(lineLen: int) -> list[int]:
"""
Returns the contribution from the scenario where two houses are either
located in the left line [1, x) or the right line (y, n].
"""
res = [0] * n
for k in range(1, lineLen + 1):
res[k - 1] += lineLen - k
return res
def lineToRing(lineLen: int, ringLen: int) -> list[int]:
"""
Returns the contribution from the scenario where one house is either
located in the left line [1, x) or the right line (y, n] and the
other house is located in the cycle.
"""
res = [0] * n
for k in range(1, lineLen + ringLen):
# min(
# at most k - 1 since we need to give 1 to the line,
# at most ringLen / 2 since for length > ringLen / 2, it can always be
# calculated as ringLen - ringLen / 2
# )
maxInRingLen = min(k - 1, ringLen // 2)
# max(at least 0, at lest k - lineLen)
minInRingLen = max(0, k - lineLen)
if minInRingLen <= maxInRingLen:
# Each ring length contributes 2 to the count due to the split of
# paths when entering the ring: One path traverses the upper half of
# the ring, and the other traverses the lower half.
# This is illustrated as follows:
# Path 1: ... -- x -- (upper half of the ring)
# Path 2: ... -- x -- (lower half of the ring)
res[k - 1] += (maxInRingLen - minInRingLen + 1) * 2
if minInRingLen == 0:
# Subtract 1 since there's no split.
res[k - 1] -= 1
if maxInRingLen * 2 == ringLen:
# Subtract 1 since the following case only contribute one:
# ... -- x -- (upper half of the ring) -- middle point
# ... -- x -- (upper half of the ring) -- middle point
res[k - 1] -= 1
return res
def lineToLine(leftLineLen: int, rightLineLen: int) -> list[int]:
"""
Returns the contribution from the scenario where one house is in the left
line [1, x) and the other house is in the right line (y, n].
"""
res = [0] * n
for k in range(leftLineLen + rightLineLen + 2):
# min(
# at most leftLineLen,
# at most k - 1 - (x < y) since we need to give 1 to the right line
# and if x < y we need to give another 1 to "x - y".
# )
maxInLeft = min(leftLineLen, k - 1 - (x < y))
# max(at least 1, at least k - rightLineLen - (x < y))
minInLeft = max(1, k - rightLineLen - (x < y))
if minInLeft <= maxInLeft:
res[k - 1] += maxInLeft - minInLeft + 1
return res
ringLen = y - x + 1
leftLineLen = x - 1
rightLineLen = (n - y)
ans = [0] * n
ans = list(map(operator.add, ans, bothInRing(ringLen)))
ans = list(map(operator.add, ans, bothInTheSameLine(leftLineLen)))
ans = list(map(operator.add, ans, bothInTheSameLine(rightLineLen)))
ans = list(map(operator.add, ans, lineToRing(leftLineLen, ringLen)))
ans = list(map(operator.add, ans, lineToRing(rightLineLen, ringLen)))
ans = list(map(operator.add, ans, lineToLine(leftLineLen, rightLineLen)))
return [freq * 2 for freq in ans]
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.