3265. Count Almost Equal Pairs I
Description
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
ory
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.
Example 1:
Input: nums = [3,12,30,17,21]
Output: 2
Explanation:
The almost equal pairs of elements are:
- 3 and 30. By swapping 3 and 0 in 30, you get 3.
- 12 and 21. By swapping 1 and 2 in 12, you get 21.
Example 2:
Input: nums = [1,1,1,1,1]
Output: 10
Explanation:
Every two elements in the array are almost equal.
Example 3:
Input: nums = [123,231]
Output: 0
Explanation:
We cannot swap any two digits of 123 or 231 to reach the other.
Constraints:
2 <= nums.length <= 100
1 <= nums[i] <= 106
Solutions
Solution 1: Sorting + Enumeration
We can enumerate each number, and for each number, we can enumerate each pair of different digits, then swap these two digits to get a new number. We record this new number in a hash table $s$, representing all possible numbers after at most one swap. Then, we count how many numbers previously enumerated are in the hash table $s$ and add this count to the answer. Next, we add the currently enumerated number to the hash table $\textit{cnt}$, representing the count of the current number.
This enumeration method may miss some pairs, such as $[100, 1]$, because the number obtained by swapping digits in $100$ is $1$, and previously enumerated numbers do not include $1$, thus missing some pairs. We can solve this problem by sorting the array before enumeration.
The time complexity is $O(n \times (\log n + \log^3 M))$, and the space complexity is $O(n + \log^2 M)$. Here, $n$ is the length of the array $\textit{nums}$, and $M$ is the maximum value in the array $\textit{nums}$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
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 |
|
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 |
|