3265. Count Almost Equal Pairs I LeetCode Solution
In this guide, you will get 3265. Count Almost Equal Pairs I LeetCode Solution with the best time and space complexity. The solution to Count Almost Equal Pairs I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Time Complexity: O(n \cdot \log(\max(\texttt{nums}))^2)
Space Complexity: O(\log(\max(\texttt{nums}))^2)
3265. Count Almost Equal Pairs I LeetCode Solution in C++
class Solution {
public:
int countPairs(vector<int>& nums) {
int ans = 0;
unordered_map<int, int> count;
const int maxLen = to_string(ranges::max(nums)).length();
for (const int num : nums) {
const string digits =
string(maxLen - to_string(num).length(), '0') + to_string(num);
for (const int swap : getSwaps(digits))
ans += count[swap];
++count[num];
}
return ans;
}
private:
// Returns all possible numbers after 1 swap.
unordered_set<int> getSwaps(const string& digits) {
const int n = digits.length();
unordered_set<int> swaps{{stoi(digits)}};
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
string newDigits = digits;
swap(newDigits[i], newDigits[j]);
swaps.insert(stoi(newDigits));
}
return swaps;
}
}; /* code provided by PROGIEZ */
3265. Count Almost Equal Pairs I LeetCode Solution in Java
class Solution {
public int countPairs(int[] nums) {
int ans = 0;
Map<Integer, Integer> count = new HashMap<>();
final int maxLen = String.valueOf(Arrays.stream(nums).max().getAsInt()).length();
for (final int num : nums) {
final String digits = String.format("%0" + maxLen + "d", num);
for (final int swap : getSwaps(digits))
ans += count.getOrDefault(swap, 0);
count.merge(num, 1, Integer::sum);
}
return ans;
}
// Returns all possible numbers after 1 swap.
private Set<Integer> getSwaps(final String digits) {
final int n = digits.length();
Set<Integer> swaps = new HashSet<>(Arrays.asList(Integer.parseInt(digits)));
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
char[] newDigits = digits.toCharArray();
char temp = newDigits[i];
newDigits[i] = newDigits[j];
newDigits[j] = temp;
swaps.add(Integer.parseInt(new String(newDigits)));
}
return swaps;
}
} // code provided by PROGIEZ
3265. Count Almost Equal Pairs I LeetCode Solution in Python
class Solution:
def countPairs(self, nums: list[int]) -> int:
ans = 0
count = collections.Counter()
maxLen = len(str(max(nums)))
for num in nums:
digits = list(str(num).zfill(maxLen))
for swap in self._getSwaps(digits):
ans += count[swap]
count[num] += 1
return ans
def _getSwaps(self, digits: str) -> set[int]:
"""Returns all possible numbers after 1 swap."""
n = len(digits)
swaps = set([int(''.join(digits))])
for i, j in itertools.combinations(range(n), 2):
newDigits = digits[:]
newDigits[i], newDigits[j] = newDigits[j], newDigits[i]
swaps.add(int(''.join(newDigits)))
return swaps # code by PROGIEZ
