diff options
author | Jack Sangdahl <[email protected]> | 2025-08-12 23:08:57 +0200 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-08-12 23:08:57 +0200 |
commit | 07680f2c668dbc7c14b36badd9dcfe59a967c78e (patch) | |
tree | 51ecad150527f707d3b0640cf9a3999862089968 | |
parent | 22ba93aab326c45f744503778d592c0623a058d5 (diff) | |
download | leetcode-07680f2c668dbc7c14b36badd9dcfe59a967c78e.tar.gz leetcode-07680f2c668dbc7c14b36badd9dcfe59a967c78e.zip |
3017. count the number of houses at a certain distance 2
-rw-r--r-- | count_number_houses_dist2.c | 69 | ||||
-rw-r--r-- | count_number_houses_dist2.py | 44 |
2 files changed, 113 insertions, 0 deletions
diff --git a/count_number_houses_dist2.c b/count_number_houses_dist2.c new file mode 100644 index 0000000..4e7c09f --- /dev/null +++ b/count_number_houses_dist2.c @@ -0,0 +1,69 @@ +// 3017. Count the Number of Houses at a Certain Distance II +#include "leetcode.h" + +/* + * you are given three positive integers 'n', 'x', and 'y'. in a city, there + * exists houses numbered 1 to 'n' connected by 'n' streets. there is a street + * cnnecting 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 '(house_i, house_j)' such that the minimum + * number of streets that need to be traveled to reach 'house_i' from 'house_j' + * is 'k'. return a 1-indexed array of length 'n' where 'ans[k]' represents the + * total number of pairs of houses such that the minimum streets required to + * reach one house from the other is 'k'. + */ + +long long *countOfPairs(int n, int x, int y, int *returnSize) { + *returnSize = n; + long long *ans = (long long *)calloc(n, sizeof(int)); + x--, y--; + if (x > y) { + int tmp = x; + x = y; + y = tmp; + } + for (int i = 0; i < n; i++) { + ans[0] += 2; + int idx1 = fmin(abs(i - x), abs(i - y) + 1); + if (idx1 < n) + ans[idx1]++; + int idx2 = fmin(abs(i - y), abs(i - x) + 1); + if (idx2 < n) + ans[idx2]++; + int idx3 = fmin(abs(i - 0), abs(i - y) + 1 + abs(x - 0)); + if (idx3 < n) + ans[idx3]--; + int idx4 = fmin(abs(i - (n - 1)), abs(i - x) + 1 + abs(y - (n - 1))); + if (idx4 < n) + ans[idx4]--; + int idx5 = fmax(x - i, 0) + fmax(i - y, 0) + ((y - x) + 0) / 2; + if (idx5 < n) + ans[idx5]--; + int idx6 = fmax(x - i, 0) + fmax(i - y, 0) + ((y - x) + 1) / 2; + if (idx6 < n) + ans[idx6]--; + } + for (int i = 1; i < n; i++) + ans[i] += ans[i - 1]; + return ans; +} + +int main() { + int rs1, rs2, rs3; + long long *cop1 = countOfPairs(3, 1, 3, &rs1); + long long *cop2 = countOfPairs(5, 2, 4, &rs2); + long long *cop3 = countOfPairs(4, 1, 1, &rs3); + for (int i = 0; i < rs1; i++) + printf("%lld ", cop1[i]); // expect: 6 0 0 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%lld ", cop2[i]); // expect: 10 8 2 0 0 + printf("\n"); + for (int i = 0; i < rs3; i++) + printf("%lld ", cop3[i]); // expect: 6 4 2 0 + printf("\n"); + free(cop1); + free(cop2); + free(cop3); +} diff --git a/count_number_houses_dist2.py b/count_number_houses_dist2.py new file mode 100644 index 0000000..5852348 --- /dev/null +++ b/count_number_houses_dist2.py @@ -0,0 +1,44 @@ +# 3017. Count the Number of Houses at a Certain Distance II +from itertools import accumulate + +""" +you are given three positive integers 'n', 'x', and 'y'. in a city, there +exists houses numbered 1 to 'n' connected by 'n' streets. there is a street +cnnecting 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 '(house_i, house_j)' such that the minimum +number of streets that need to be traveled to reach 'house_i' from 'house_j' +is 'k'. return a 1-indexed array of length 'n' where 'ans[k]' represents the +total number of pairs of houses such that the minimum streets required to +reach one house from the other is 'k'. +""" + + +class Solution(object): + def countOfPairs(self, n, x, y): + """ + :type n: int + :type x: int + :type y: int + :rtype: List[int] + """ + x, y = min(x, y), max(x, y) + ans = [0] * n + for i in range(1, n + 1): + ans[0] += 2 + ans[min(i - 1, abs(i - y) + x)] -= 1 + ans[min(n - i, abs(i - x) + 1 + n - y)] -= 1 + ans[min(abs(i - x), abs(y - i) + 1)] += 1 + ans[min(abs(i - x) + 1, abs(y - i))] += 1 + r = max(x - i, 0) + max(i - y, 0) + ans[r + (y - x + 0) // 2] -= 1 + ans[r + (y - x + 1) // 2] -= 1 + return list(accumulate(ans)) + + +if __name__ == "__main__": + obj = Solution() + print(obj.countOfPairs(n=3, x=1, y=3)) + print(obj.countOfPairs(n=5, x=2, y=4)) + print(obj.countOfPairs(n=4, x=1, y=1)) |