Hash Solution, C
Intuition\nTo solve the problem of finding pairs of "almost equal" numbers in the array, we can use a hash table. The idea is to generate all possible numbers t
# Intuition\nTo solve the problem of finding pairs of "almost equal" numbers in the array, we can use a hash table. The idea is to generate all possible numbers that can be formed by swapping up to two pairs of digits in each number and check if they exist in the hash table. By storing previously encountered numbers in the hash table, we can quickly identify and count valid pairs involving the current number and its variations.\n\n# Approach\n1. **Initialize the Hash Table:** Start by initializing a hash table to store each number from the array along with its occurrence count as it is processed.\n2. **Process Each Number:**\n    - Check the Original Number: For each number in the array, first check if it exists in the hash table. If it does, add its count to the result (since this represents a valid "almost equal" pair with itself) and increment the count in the hash table.\n    - Generate All Possible 2-Digit Swaps: For each number, generate all possible numbers that can be formed by swapping any two digits.   For each swapped number:\n        - Check if it exists in the hash table.\n        - If it does, ensure it hasn\u2019t been counted already for the current number (using a marking system to track this). If it hasn\u2019t been counted, add its count to the result and mark it to avoid double-counting.\n    - Handle Multiple Swaps: Consider additional swaps to handle cases where swapping two different pairs of digits might create different valid pairs.\n3. **Clear the Hash Table:** After processing all numbers, clear the hash table to release memory resources.\n\n# Complexity\nLet $$n$$ be the number of elements in array `nums`. Let $$d$$ be the number of maximum digits.\n- Time complexity: $$O(n \\times d^4)$$\n    - Traversing through every elements in array nums and check every possible 2 digit swap: $$O(n\xD7d^4)$$\n    - Clearing hash table: $$O(n)$$\n- Space complexity: $$O(n)$$\n    - For hash table: $$O(n)$$\n    - Other auxiliary variables: $$O(1)$$\n\n# Code 1\n``` C []\nint countPairs(int* nums, int numsSize) {\n    int swapped, res = 0, pow10[7] = {1000000, 100000, 10000, 1000, 100, 10, 1};\n    short i;\n    int8_t s1a, s1b, s2a, s2b, d1a, d1b, d2a, d2b;\n\n    struct HashTable{\n        int num;\n        short count, mark;\n        UT_hash_handle hh;\n    } *hashTable = NULL, *item;\n\n    for(i = 0; i < numsSize; i++){\n        swapped = nums[i];\n        \n        HASH_FIND_INT(hashTable, &swapped, item);\n        if(item) res += item->count++;\n        else{\n            item = (struct HashTable*)malloc(sizeof(struct HashTable));\n\n            item->num = swapped;\n            item->count = 1;\n            item->mark = -1;\n\n            HASH_ADD_INT(hashTable, num, item);\n        }\n\n        for(s1a = 0; s1a < 6; s1a++){\n            for(s1b = s1a + 1; s1b < 7; s1b++){\n                d1a = swapped / pow10[s1a] % 10;\n                d1b = swapped / pow10[s1b] % 10;\n\n                if(d1a != d1b){\n                    swapped -= d1a * pow10[s1a], swapped += d1b * pow10[s1a];\n                    swapped -= d1b * pow10[s1b], swapped += d1a * pow10[s1b];\n\n                    HASH_FIND_INT(hashTable, &swapped, item);\n                    if(item && item->mark != i)\n                        res += item->count, item->mark = i;\n\n                    for(s2a = s1a + 1; s2a < 6; s2a++){\n                        for(s2b = s2a + 1; s2b < 7; s2b++){\n                            d2a = swapped / pow10[s2a] % 10;\n                            d2b = swapped / pow10[s2b] % 10;\n\n                            if(d2a != d2b){\n                                swapped -= d2a * pow10[s2a], swapped += d2b * pow10[s2a];\n                                swapped -= d2b * pow10[s2b], swapped += d2a * pow10[s2b];\n\n                                HASH_FIND_INT(hashTable, &swapped, item);\n                                if(item && item->mark != i)\n                                    res += item->count, item->mark = i;\n                                \n                                swapped -= d2a * pow10[s2b], swapped += d2b * pow10[s2b];\n                                swapped -= d2b * pow10[s2a], swapped += d2a * pow10[s2a];\n                            }\n                        }\n                    }\n                    \n                    swapped -= d1a * pow10[s1b], swapped += d1b * pow10[s1b];\n                    swapped -= d1b * pow10[s1a], swapped += d1a * pow10[s1a];\n                }\n            }\n        }\n    }\n\n    HASH_CLEAR(hh, hashTable);\n    return res;\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    int countPairs(vector<int>& nums) {\n        int swapped, res = 0, pow10[7] = {1000000, 100000, 10000, 1000, 100, 10, 1};\n        int8_t s1a, s1b, s2a, s2b, d1a, d1b, d2a, d2b;\n\n        unordered_map<int, pair<short, short>> hashTable;\n\n        for(short i, n = nums.size(); i < n; i++){\n            swapped = nums[i];\n\n            res += hashTable[swapped].first++;\n\n            for(s1a = 0; s1a < 6; s1a++){\n                for(s1b = s1a + 1; s1b < 7; s1b++){\n                    d1a = swapped / pow10[s1a] % 10;\n                    d1b = swapped / pow10[s1b] % 10;\n\n                    if(d1a != d1b){\n                        swapped += (d1b - d1a) * pow10[s1a] + (d1a - d1b) * pow10[s1b];\n\n                        if(hashTable.find(swapped) != hashTable.end() && hashTable[swapped].second != i)\n                            res += hashTable[swapped].first, hashTable[swapped].second = i;\n\n                        for(s2a = s1a + 1; s2a < 6; s2a++){\n                            for(s2b = s2a + 1; s2b < 7; s2b++){\n                                d2a = swapped / pow10[s2a] % 10;\n                                d2b = swapped / pow10[s2b] % 10;\n                                \n                                if(d2a != d2b){\n                                    swapped += (d2b - d2a) * pow10[s2a] + (d2a - d2b) * pow10[s2b];\n\n                                    if(hashTable.find(swapped) != hashTable.end() && hashTable[swapped].second != i)\n                                        res += hashTable[swapped].first, hashTable[swapped].second = i;\n                                    \n                                    swapped += (d2b - d2a) * pow10[s2b] + (d2a - d2b) * pow10[s2a];\n\n                                }\n                            }\n                        }\n                        \n                        swapped += (d1b - d1a) * pow10[s1b] + (d1a - d1b) * pow10[s1a];\n                    }\n                }\n            }\n        }\n\n        return res;\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int countPairs(int[] nums) {\n        int swapped, res = 0;\n        int[] pow10 = {1000000, 100000, 10000, 1000, 100, 10, 1};\n        byte s1a, s1b, s2a, s2b, d1a, d1b, d2a, d2b;\n\n        HashMap<Integer, Pair<Short, Short>> hashTable = new HashMap<Integer, Pair<Short, Short>>();\n        Pair<Short, Short> entry;\n\n        for(short i = 0, n = (short) nums.length; i < n; i++){\n            swapped = nums[i];\n\n            entry = hashTable.getOrDefault(swapped, new Pair<>((short) 0, (short) 0));\n            res += entry.getKey();\n            hashTable.put(swapped, new Pair<>((short) (entry.getKey() + 1), (short) entry.getValue()));\n\n            for(s1a = 0; s1a < 6; s1a++){\n                for(s1b = (byte) (s1a + 1); s1b < 7; s1b++){\n                    d1a = (byte) (swapped / pow10[s1a] % 10);\n                    d1b = (byte) (swapped / pow10[s1b] % 10);\n\n                    if(d1a != d1b){\n                        swapped += (d1b - d1a) * pow10[s1a] + (d1a - d1b) * pow10[s1b];\n\n                        entry = hashTable.getOrDefault(swapped, new Pair<>((short) 0, (short) 0));\n                        if(entry.getKey() > 0 && entry.getValue() != i){\n                            res += entry.getKey();\n                            hashTable.put(swapped, new Pair<>((short) entry.getKey(), i));\n                        }\n\n                        for(s2a = (byte) (s1a + 1); s2a < 6; s2a++){\n                            for(s2b = (byte) (s2a + 1); s2b < 7; s2b++){\n                                d2a = (byte) (swapped / pow10[s2a] % 10);\n                                d2b = (byte) (swapped / pow10[s2b] % 10);\n\n                                if(d2a != d2b){\n                                    swapped += (d2b - d2a) * pow10[s2a] + (d2a - d2b) * pow10[s2b];\n\n                                    entry = hashTable.getOrDefault(swapped, new Pair<>((short) 0, (short) 0));\n                                    if(entry.getKey() > 0 && entry.getValue() != i){\n                                        res += entry.getKey();\n                                        hashTable.put(swapped, new Pair<>((short) entry.getKey(), i));\n                                    }\n                                    \n                                    swapped += (d2b - d2a) * pow10[s2b] + (d2a - d2b) * pow10[s2a];\n                                }\n                            }\n                        }\n\n                        swapped += (d1b - d1a) * pow10[s1b] + (d1a - d1b) * pow10[s1a];\n                    }\n                }\n            }\n        }\n\n        return res;\n    }\n}\n```\n``` Python3 []\nclass Solution:\n    def countPairs(self, nums: List[int]) -> int:\n        pow10 = (1000000, 100000, 10000, 1000, 100, 10, 1)\n\n        hashTable = {}\n\n        res, n = 0, len(nums)\n        for i in range(n):\n            swapped = nums[i]\n\n            entry = hashTable.get(swapped, (0, 0))\n            res += entry[0]\n            hashTable[swapped] = (entry[0] + 1, entry[1])\n\n            for s1a in range(6):\n                for s1b in range(s1a + 1, 7):\n                    d1a = int(swapped / pow10[s1a] % 10)\n                    d1b = int(swapped / pow10[s1b] % 10)\n\n                    if d1a != d1b:\n                        swapped += (d1b - d1a) * pow10[s1a] + (d1a - d1b) * pow10[s1b]\n\n                        entry = hashTable.get(swapped, (0, 0))\n                        if entry[0] > 0 and entry[1] != i:\n                            res += entry[0]\n                            hashTable[swapped] = (entry[0], i)\n\n                        for s2a in range(s1a + 1, 6):\n                            for s2b in range(s2a + 1, 7):\n                                d2a = int(swapped / pow10[s2a] % 10)\n                                d2b = int(swapped / pow10[s2b] % 10)\n\n                                if d2a != d2b:\n                                    swapped += (d2b - d2a) * pow10[s2a] + (d2a - d2b) * pow10[s2b]\n\n                                    entry = hashTable.get(swapped, (0, 0))\n                                    if entry[0] > 0 and entry[1] != i:\n                                        res += entry[0]\n                                        hashTable[swapped] = (entry[0], i)\n\n                                    swapped += (d2b - d2a) * pow10[s2b] + (d2a - d2b) * pow10[s2a]\n\n                        swapped += (d1b - d1a) * pow10[s1b] + (d1a - d1b) * pow10[s1a]\n\n        return res\n```\n# Code 2 (String Conversion)\nNote: This code is slower than the previous code.\n``` C []\nint countPairs(int* nums, int numsSize) {\n    char swap, *strForm = (char*)malloc(8);\n    short i, j, s1a, s1b, s2a, s2b;\n    int dig, res = 0;\n\n    struct HashTable{\n        char *num;\n        short count, mark;\n        UT_hash_handle hh;\n    } *hashTable = NULL, *item, *tmp;\n\n    for(i = 0, strForm[7] = \'\\0\'; i < numsSize; i++){\n        for(dig = 1000000, j = 0; dig > 0; dig /= 10, j++)\n            strForm[j] = (nums[i] / dig % 10) + \'0\';\n        \n        HASH_FIND_STR(hashTable, strForm, item);\n        if(item) res += item->count++;\n        else{\n            item = (struct HashTable*)malloc(sizeof(struct HashTable));\n            item->num = (char*)malloc(8);\n\n            for(int8_t i = 0; i < 8; i++)\n                item->num[i] = strForm[i];\n            item->count = 1;\n            item->mark = -1;\n\n            HASH_ADD_STR(hashTable, num, item);\n        }\n\n        for(s1a = 0; s1a < 6; s1a++){\n            for(s1b = s1a + 1; s1b < 7; s1b++){\n                if(strForm[s1a] != strForm[s1b]){\n                    swap = strForm[s1b], strForm[s1b] = strForm[s1a], strForm[s1a] = swap;\n\n                    HASH_FIND_STR(hashTable, strForm, item);\n                    if(item && item->mark != i)\n                        res += item->count, item->mark = i;\n\n                    for(s2a = s1a + 1; s2a < 6; s2a++){\n                        for(s2b = s2a + 1; s2b < 7; s2b++){\n                            if(strForm[s2a] != strForm[s2b]){\n                                swap = strForm[s2b], strForm[s2b] = strForm[s2a], strForm[s2a] = swap;\n                                HASH_FIND_STR(hashTable, strForm, item);\n                                if(item && item->mark != i)\n                                    res += item->count, item->mark = i;\n                                swap = strForm[s2b], strForm[s2b] = strForm[s2a], strForm[s2a] = swap;\n                            }\n                        }\n                    }\n                    \n                    swap = strForm[s1b], strForm[s1b] = strForm[s1a], strForm[s1a] = swap;\n                }\n            }\n        }\n    }\n\n    free(strForm);\n    HASH_ITER(hh, hashTable, item, tmp){\n        HASH_DEL(hashTable, item);\n        free(item->num);\n        free(item);\n    }\n    return res;\n}\n```\n``` Python3 []\nclass Solution:\n    def countPairs(self, nums: List[int]) -> int:\n        hashTable = {}\n\n        res, n = 0, len(nums)\n        for i in range(n):\n            swapped = str(nums[i])\n            swapped = \'0\' * (7 - len(swapped)) + swapped\n\n            entry = hashTable.get(swapped, (0, 0))\n            res += entry[0]\n            hashTable[swapped] = (entry[0] + 1, entry[1])\n\n            for s1a in range(6):\n                for s1b in range(s1a + 1, 7):\n                    if swapped[s1a] != swapped[s1b]:\n                        swapped = swapped[:s1a] + swapped[s1b] + swapped[s1a + 1:s1b] + swapped[s1a] + swapped[s1b + 1:]\n\n                        entry = hashTable.get(swapped, (0, 0))\n                        if entry[0] > 0 and entry[1] != i:\n                            res += entry[0]\n                            hashTable[swapped] = (entry[0], i)\n\n                        for s2a in range(s1a + 1, 6):\n                            for s2b in range(s2a + 1, 7):\n                                if swapped[s2a] != swapped[s2b]:\n                                    swapped = swapped[:s2a] + swapped[s2b] + swapped[s2a + 1:s2b] + swapped[s2a] + swapped[s2b + 1:]\n\n                                    entry = hashTable.get(swapped, (0, 0))\n                                    if entry[0] > 0 and entry[1] != i:\n                                        res += entry[0]\n                                        hashTable[swapped] = (entry[0], i)\n\n                                    swapped = swapped[:s2a] + swapped[s2b] + swapped[s2a + 1:s2b] + swapped[s2a] + swapped[s2b + 1:]\n\n                        swapped = swapped[:s1a] + swapped[s1b] + swapped[s1a + 1:s1b] + swapped[s1a] + swapped[s1b + 1:]\n\n        return res\n```
['Hash Table', 'String', 'C', 'Hash Function', 'C++', 'Java', 'Python3']