aboutsummaryrefslogtreecommitdiff
path: root/count_number_houses_dist2.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-08-12 23:08:57 +0200
committerJack Sangdahl <[email protected]>2025-08-12 23:08:57 +0200
commit07680f2c668dbc7c14b36badd9dcfe59a967c78e (patch)
tree51ecad150527f707d3b0640cf9a3999862089968 /count_number_houses_dist2.c
parent22ba93aab326c45f744503778d592c0623a058d5 (diff)
downloadleetcode-07680f2c668dbc7c14b36badd9dcfe59a967c78e.tar.gz
leetcode-07680f2c668dbc7c14b36badd9dcfe59a967c78e.zip
3017. count the number of houses at a certain distance 2
Diffstat (limited to 'count_number_houses_dist2.c')
-rw-r--r--count_number_houses_dist2.c69
1 files changed, 69 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);
+}