aboutsummaryrefslogtreecommitdiff
path: root/count_equal_pairs1.c
blob: b690634212d5915a8ccc5654e9df4b8f155e6ffd (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
// 3265. Count Almost Equal Pairs I
#include "leetcode.h"

/*
 * you are given an array 'nums' consisting of positive integers. we call two
 * integers 'x' and 'y' in this problem almost equal if both integers can become
 * equal after performing the following operation at most once: choose either
 * 'x' or 'y' and swap any two digits within the chosen number. return the
 * number of indices 'i' and 'j' in 'nums' where 'i < j' such that 'nums[i]' and
 * 'nums[j]' are almost equal. note that it is allowed for an integer to have
 * leading zeros after performing an operation.
 */

struct hash {
  int num;
  int8_t count;
  UT_hash_handle hh;
};

int countPairs(int *nums, int numsSize) {
  int ans = 0, swapped, pow10[7] = {1000000, 100000, 10000, 1000, 100, 10, 1};
  struct hash *table = NULL, *item;
  for (int i = 0; i < numsSize; i++) {
    swapped = nums[i];
    HASH_FIND_INT(table, &swapped, item);
    if (item)
      ans += item->count++;
    else {
      item = (struct hash *)malloc(sizeof(struct hash));
      item->num = swapped;
      item->count = 1;
      HASH_ADD_INT(table, num, item);
    }
    for (int j = 0; j < 6; j++)
      for (int k = j + 1; k < 7; k++) {
        int n = swapped / pow10[j] % 10;
        int m = swapped / pow10[k] % 10;
        if (n != m) {
          swapped -= n * pow10[j];
          swapped += m * pow10[j];
          swapped -= m * pow10[k];
          swapped += n * pow10[k];
          HASH_FIND_INT(table, &swapped, item);
          ans += item ? item->count : 0;
          swapped -= n * pow10[k];
          swapped += m * pow10[k];
          swapped -= m * pow10[j];
          swapped += n * pow10[j];
        }
      }
  }
  HASH_CLEAR(hh, table);
  return ans;
}

int main() {
  int n1[] = {3, 12, 30, 17, 21}, n2[] = {1, 1, 1, 1, 1}, n3[] = {123, 231};
  printf("%d\n", countPairs(n1, ARRAY_SIZE(n1))); // expect: 2
  printf("%d\n", countPairs(n2, ARRAY_SIZE(n2))); // expect: 10
  printf("%d\n", countPairs(n3, ARRAY_SIZE(n3))); // expect: 0
}