aboutsummaryrefslogtreecommitdiff
path: root/count_number_houses_dist2.c
blob: 4e7c09f67dd0a17a969b5ab79d76217d62a9798f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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);
}