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:
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:
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 <= 1001 <= nums[i] <= 106Two numbers can be almost equal if the frequency of each digit is the same, with at most one anomaly to allow a single swap. We can use this idea to compare each pair of numbers.
The approach is to go through each pair of numbers, calculate the frequency of each digit (0-9), and check if the number frequencies are similar when allowing one mismatched pair.
This solution compares the digit frequency of two numbers using the Counter class and checks if they can be made equal by allowing a single swap. The key operation checks if the absolute differences between digit counts are minor when summed.
Java
Time Complexity: O(n^2 * k) where n is the number of elements and k is the maximum number of digits in a number.
Space Complexity: O(1) for fixed size Counter handling from 0 to 9.
This approach directly considers whether the digits of one number can be rearranged to form another without explicitly counting mismatches. It essentially checks if two numbers are permutations allowing a single swap.
The method involves generating a list of permutations and comparing against the other number.
This JavaScript solution creates a set of permutations for each number and checks against subsequent numbers if they can be generated by permutations, storing them in a set to compare.
Time Complexity: Complex due to heavy permutation generation; exponential nature is expected (O(n!)) for digits per input number.
Space Complexity: O(permutations generated).
| Approach | Complexity |
|---|---|
| Digit Frequency Comparison | Time Complexity: O(n^2 * k) where n is the number of elements and k is the maximum number of digits in a number. |
| Direct Permutation Check | Time Complexity: Complex due to heavy permutation generation; exponential nature is expected (O(n!)) for digits per input number. |
Count the Number of Fair Pairs - Leetcode 2563 - Python • NeetCodeIO • 15,313 views views
Watch 9 more video solutions →Practice Count Almost Equal Pairs I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor