diff options
author | Jack Sangdahl <[email protected]> | 2025-03-01 12:53:59 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-01 12:53:59 -0700 |
commit | d244407ce1f87bc1bd01cd3199cc179433582e70 (patch) | |
tree | ced8d7f6f619d0a27c5e979d0a7aca1aaafe5d72 | |
parent | bf357e5cbc5730591b60379006396ea613ba4987 (diff) | |
download | leetcode-d244407ce1f87bc1bd01cd3199cc179433582e70.tar.gz leetcode-d244407ce1f87bc1bd01cd3199cc179433582e70.zip |
3265. count almost equal pairs 1
-rw-r--r-- | count_equal_pairs1.c | 61 | ||||
-rw-r--r-- | count_equal_pairs1.py | 41 |
2 files changed, 102 insertions, 0 deletions
diff --git a/count_equal_pairs1.c b/count_equal_pairs1.c new file mode 100644 index 0000000..b690634 --- /dev/null +++ b/count_equal_pairs1.c @@ -0,0 +1,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 +} diff --git a/count_equal_pairs1.py b/count_equal_pairs1.py new file mode 100644 index 0000000..177b3ce --- /dev/null +++ b/count_equal_pairs1.py @@ -0,0 +1,41 @@ +# 3265. Count Almost Equal Pairs I + +""" +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. +""" + + +class Solution(object): + def countPairs(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + pow10 = [1000000, 100000, 10000, 1000, 100, 10, 1] + table, ans = {}, 0 + for swapped in nums: + cnt = table.get(swapped, 0) + table[swapped] = cnt + 1 + ans += cnt + for j in range(6): + for k in range(j + 1, 7): + n = int(swapped / pow10[j] % 10) + m = int(swapped / pow10[k] % 10) + if n != m: + swapped += (m - n) * pow10[j] + (n - m) * pow10[k] + ans += table.get(swapped, 0) + swapped += (m - n) * pow10[k] + (n - m) * pow10[j] + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countPairs(nums=[3, 12, 30, 17, 21])) + print(obj.countPairs(nums=[1, 1, 1, 1, 1])) + print(obj.countPairs(nums=[123, 231])) |